0000: 2f 2f 20 54 65 73 74 65 64 3a 20 53 52 4d 20 34 // Tested: SRM 4
0010: 35 34 20 4c 76 32 0a 74 65 6d 70 6c 61 74 65 3c 54 Lv2.template<
0020: 74 79 70 65 6e 61 6d 65 20 54 3e 0a 73 74 72 75 typename T>.stru
0030: 63 74 20 44 50 32 0a 7b 0a 09 63 6f 6e 73 74 20 ct DP2.{..const
0040: 69 6e 74 20 4e 31 2c 20 4e 32 3b 0a 09 76 65 63 int N1, N2;..vec
0050: 74 6f 72 3c 54 3e 20 64 61 74 61 3b 0a 09 44 50 tor<T> data;..DP
0060: 32 28 69 6e 74 20 4e 31 2c 20 69 6e 74 20 4e 32 2(int N1, int N2
0070: 2c 20 63 6f 6e 73 74 20 54 26 20 74 20 3d 20 54 , const T& t = T
0080: 28 29 29 0a 09 09 3a 20 4e 31 28 4e 31 29 2c 20 ())...: N1(N1),
0090: 4e 32 28 4e 32 29 2c 20 64 61 74 61 28 4e 31 2a N2(N2), data(N1*
00a0: 4e 32 2c 20 74 29 20 7b 20 61 73 73 65 72 74 28 N2, t) { assert(
00b0: 64 61 74 61 2e 73 69 7a 65 28 29 2a 73 69 7a 65 data.size()*size
00c0: 6f 66 28 54 29 3c 28 31 3c 3c 32 36 29 29 3b 20 of(T)<(1<<26));
00d0: 7d 0a 09 54 26 20 6f 70 65 72 61 74 6f 72 28 29 }..T& operator()
00e0: 28 69 6e 74 20 69 31 2c 20 69 6e 74 20 69 32 29 (int i1, int i2)
00f0: 0a 09 09 7b 20 72 65 74 75 72 6e 20 64 61 74 61 ...{ return data
0100: 5b 20 28 69 31 2a 4e 32 29 2b 69 32 20 5d 3b 20 [ (i1*N2)+i2 ];
0110: 7d 0a 09 76 6f 69 64 20 73 77 61 70 28 44 50 32 }..void swap(DP2
0120: 26 20 72 68 73 29 0a 09 09 7b 20 64 61 74 61 2e & rhs)...{ data.
0130: 73 77 61 70 28 72 68 73 2e 64 61 74 61 29 3b 20 swap(rhs.data);
0140: 7d 0a 7d 3b 0a 0a 2f 2f 20 54 65 73 74 65 64 3a }.};..// Tested:
0150: 20 43 6f 64 65 66 6f 72 63 65 73 20 23 31 33 20 Codeforces #13
0160: 43 0a 74 65 6d 70 6c 61 74 65 3c 74 79 70 65 6e C.template<typen
0170: 61 6d 65 20 54 3e 0a 73 74 72 75 63 74 20 44 50 ame T>.struct DP
0180: 32 78 0a 7b 0a 09 63 6f 6e 73 74 20 69 6e 74 20 2x.{..const int
0190: 4e 31 2c 20 4e 32 3b 0a 09 76 65 63 74 6f 72 3c N1, N2;..vector<
01a0: 54 3e 20 64 61 74 61 3b 0a 09 44 50 32 78 28 69 T> data;..DP2x(i
01b0: 6e 74 2c 20 69 6e 74 20 4e 32 2c 20 63 6f 6e 73 nt, int N2, cons
01c0: 74 20 54 26 20 74 20 3d 20 54 28 29 29 0a 09 09 t T& t = T())...
01d0: 3a 20 4e 31 28 32 29 2c 20 4e 32 28 4e 32 29 2c : N1(2), N2(N2),
01e0: 20 64 61 74 61 28 4e 31 2a 4e 32 2c 20 74 29 20 data(N1*N2, t)
01f0: 7b 20 61 73 73 65 72 74 28 64 61 74 61 2e 73 69 { assert(data.si
0200: 7a 65 28 29 2a 73 69 7a 65 6f 66 28 54 29 3c 28 ze()*sizeof(T)<(
0210: 31 3c 3c 32 36 29 29 3b 20 7d 0a 09 54 26 20 6f 1<<26)); }..T& o
0220: 70 65 72 61 74 6f 72 28 29 28 69 6e 74 20 69 31 perator()(int i1
0230: 2c 20 69 6e 74 20 69 32 29 0a 09 09 7b 20 69 31 , int i2)...{ i1
0240: 26 3d 31 3b 20 72 65 74 75 72 6e 20 64 61 74 61 &=1; return data
0250: 5b 20 28 69 31 2a 4e 32 29 2b 69 32 20 5d 3b 20 [ (i1*N2)+i2 ];
0260: 7d 0a 09 76 6f 69 64 20 73 77 61 70 28 44 50 32 }..void swap(DP2
0270: 78 26 20 72 68 73 29 0a 09 09 7b 20 64 61 74 61 x& rhs)...{ data
0280: 2e 73 77 61 70 28 72 68 73 2e 64 61 74 61 29 3b .swap(rhs.data);
0290: 20 7d 0a 7d 3b 0a 0a 2f 2f 20 54 65 73 74 65 64 }.};..// Tested
02a0: 3a 20 53 52 4d 20 34 35 32 20 4c 76 33 0a 74 65 : SRM 452 Lv3.te
02b0: 6d 70 6c 61 74 65 3c 74 79 70 65 6e 61 6d 65 20 mplate<typename
02c0: 54 3e 0a 73 74 72 75 63 74 20 44 50 33 0a 7b 0a T>.struct DP3.{.
02d0: 09 69 6e 74 20 4e 31 2c 20 4e 32 2c 20 4e 33 3b .int N1, N2, N3;
02e0: 0a 09 76 65 63 74 6f 72 3c 54 3e 20 64 61 74 61 ..vector<T> data
02f0: 3b 0a 09 44 50 33 28 69 6e 74 20 4e 31 2c 20 69 ;..DP3(int N1, i
0300: 6e 74 20 4e 32 2c 20 69 6e 74 20 4e 33 2c 20 63 nt N2, int N3, c
0310: 6f 6e 73 74 20 54 26 20 74 20 3d 20 54 28 29 29 onst T& t = T())
0320: 0a 09 09 3a 20 4e 31 28 4e 31 29 2c 20 4e 32 28 ...: N1(N1), N2(
0330: 4e 32 29 2c 20 4e 33 28 4e 33 29 2c 20 64 61 74 N2), N3(N3), dat
0340: 61 28 4e 31 2a 4e 32 2a 4e 33 2c 20 74 29 20 7b a(N1*N2*N3, t) {
0350: 20 61 73 73 65 72 74 28 64 61 74 61 2e 73 69 7a assert(data.siz
0360: 65 28 29 2a 73 69 7a 65 6f 66 28 54 29 3c 28 31 e()*sizeof(T)<(1
0370: 3c 3c 32 36 29 29 3b 20 7d 0a 09 54 26 20 6f 70 <<26)); }..T& op
0380: 65 72 61 74 6f 72 28 29 28 69 6e 74 20 69 31 2c erator()(int i1,
0390: 20 69 6e 74 20 69 32 2c 20 69 6e 74 20 69 33 29 int i2, int i3)
03a0: 0a 09 09 7b 20 72 65 74 75 72 6e 20 64 61 74 61 ...{ return data
03b0: 5b 20 28 28 69 31 2a 4e 32 29 2b 69 32 29 2a 4e [ ((i1*N2)+i2)*N
03c0: 33 2b 69 33 20 5d 3b 20 7d 0a 09 76 6f 69 64 20 3+i3 ]; }..void
03d0: 73 77 61 70 28 44 50 33 26 20 72 68 73 29 0a 09 swap(DP3& rhs)..
03e0: 09 7b 20 64 61 74 61 2e 73 77 61 70 28 72 68 73 .{ data.swap(rhs
03f0: 2e 64 61 74 61 29 3b 20 7d 0a 7d 3b 0a 0a 2f 2f .data); }.};..//
0400: 20 54 65 73 74 65 64 3a 20 53 52 4d 20 34 36 38 Tested: SRM 468
0410: 20 4c 76 32 0a 74 65 6d 70 6c 61 74 65 3c 74 79 Lv2.template<ty
0420: 70 65 6e 61 6d 65 20 54 3e 0a 73 74 72 75 63 74 pename T>.struct
0430: 20 44 50 33 78 0a 7b 0a 09 69 6e 74 20 4e 31 2c DP3x.{..int N1,
0440: 20 4e 32 2c 20 4e 33 3b 0a 09 76 65 63 74 6f 72 N2, N3;..vector
0450: 3c 54 3e 20 64 61 74 61 3b 0a 09 44 50 33 78 28 <T> data;..DP3x(
0460: 69 6e 74 2c 20 69 6e 74 20 4e 32 2c 20 69 6e 74 int, int N2, int
0470: 20 4e 33 2c 20 63 6f 6e 73 74 20 54 26 20 74 20 N3, const T& t
0480: 3d 20 54 28 29 29 0a 09 09 3a 20 4e 31 28 32 29 = T())...: N1(2)
0490: 2c 20 4e 32 28 4e 32 29 2c 20 4e 33 28 4e 33 29 , N2(N2), N3(N3)
04a0: 2c 20 64 61 74 61 28 4e 31 2a 4e 32 2a 4e 33 2c , data(N1*N2*N3,
04b0: 20 74 29 20 7b 20 61 73 73 65 72 74 28 64 61 74 t) { assert(dat
04c0: 61 2e 73 69 7a 65 28 29 2a 73 69 7a 65 6f 66 28 a.size()*sizeof(
04d0: 54 29 20 3c 20 28 31 3c 3c 32 36 29 29 3b 20 7d T) < (1<<26)); }
04e0: 0a 09 54 26 20 6f 70 65 72 61 74 6f 72 28 29 28 ..T& operator()(
04f0: 69 6e 74 20 69 31 2c 20 69 6e 74 20 69 32 2c 20 int i1, int i2,
0500: 69 6e 74 20 69 33 29 0a 09 09 7b 20 69 31 26 3d int i3)...{ i1&=
0510: 31 3b 20 72 65 74 75 72 6e 20 64 61 74 61 5b 20 1; return data[
0520: 28 28 69 31 2a 4e 32 29 2b 69 32 29 2a 4e 33 2b ((i1*N2)+i2)*N3+
0530: 69 33 20 5d 3b 20 7d 0a 09 76 6f 69 64 20 73 77 i3 ]; }..void sw
0540: 61 70 28 44 50 33 78 26 20 72 68 73 29 0a 09 09 ap(DP3x& rhs)...
0550: 7b 20 64 61 74 61 2e 73 77 61 70 28 72 68 73 2e { data.swap(rhs.
0560: 64 61 74 61 29 3b 20 7d 0a 7d 3b 0a 0a 2f 2f 20 data); }.};..//
0570: 4e 6f 74 20 54 65 73 74 65 64 0a 74 65 6d 70 6c Not Tested.templ
0580: 61 74 65 3c 74 79 70 65 6e 61 6d 65 20 54 3e 0a ate<typename T>.
0590: 73 74 72 75 63 74 20 44 50 34 0a 7b 0a 09 69 6e struct DP4.{..in
05a0: 74 20 4e 31 2c 20 4e 32 2c 20 4e 33 2c 20 4e 34 t N1, N2, N3, N4
05b0: 3b 0a 09 76 65 63 74 6f 72 3c 54 3e 20 64 61 74 ;..vector<T> dat
05c0: 61 3b 0a 09 44 50 34 28 69 6e 74 20 4e 31 2c 20 a;..DP4(int N1,
05d0: 69 6e 74 20 4e 32 2c 20 69 6e 74 20 4e 33 2c 20 int N2, int N3,
05e0: 69 6e 74 20 4e 34 2c 20 63 6f 6e 73 74 20 54 26 int N4, const T&
05f0: 20 74 20 3d 20 54 28 29 29 0a 09 09 3a 20 4e 31 t = T())...: N1
0600: 28 4e 31 29 2c 20 4e 32 28 4e 32 29 2c 20 4e 33 (N1), N2(N2), N3
0610: 28 4e 33 29 2c 20 4e 34 28 4e 34 29 2c 20 64 61 (N3), N4(N4), da
0620: 74 61 28 4e 31 2a 4e 32 2a 4e 33 2a 4e 34 2c 20 ta(N1*N2*N3*N4,
0630: 74 29 20 7b 20 61 73 73 65 72 74 28 64 61 74 61 t) { assert(data
0640: 2e 73 69 7a 65 28 29 2a 73 69 7a 65 6f 66 28 54 .size()*sizeof(T
0650: 29 3c 28 31 3c 3c 32 36 29 29 3b 20 7d 0a 09 54 )<(1<<26)); }..T
0660: 26 20 6f 70 65 72 61 74 6f 72 28 29 28 69 6e 74 & operator()(int
0670: 20 69 31 2c 20 69 6e 74 20 69 32 2c 20 69 6e 74 i1, int i2, int
0680: 20 69 33 2c 20 69 6e 74 20 69 34 29 0a 09 09 7b i3, int i4)...{
0690: 20 72 65 74 75 72 6e 20 64 61 74 61 5b 20 28 28 return data[ ((
06a0: 28 69 31 2a 4e 32 29 2b 69 32 29 2a 4e 33 2b 69 (i1*N2)+i2)*N3+i
06b0: 33 29 2a 4e 34 2b 69 34 20 5d 3b 20 7d 0a 09 76 3)*N4+i4 ]; }..v
06c0: 6f 69 64 20 73 77 61 70 28 44 50 34 26 20 72 68 oid swap(DP4& rh
06d0: 73 29 0a 09 09 7b 20 64 61 74 61 2e 73 77 61 70 s)...{ data.swap
06e0: 28 72 68 73 2e 64 61 74 61 29 3b 20 7d 0a 7d 3b (rhs.data); }.};
06f0: 0a 0a 2f 2f 20 4e 6f 74 20 54 65 73 74 65 64 0a ..// Not Tested.
0700: 74 65 6d 70 6c 61 74 65 3c 74 79 70 65 6e 61 6d template<typenam
0710: 65 20 54 3e 0a 73 74 72 75 63 74 20 44 50 34 78 e T>.struct DP4x
0720: 0a 7b 0a 09 69 6e 74 20 4e 31 2c 20 4e 32 2c 20 .{..int N1, N2,
0730: 4e 33 2c 20 4e 34 3b 0a 09 76 65 63 74 6f 72 3c N3, N4;..vector<
0740: 54 3e 20 64 61 74 61 3b 0a 09 44 50 34 78 28 69 T> data;..DP4x(i
0750: 6e 74 2c 20 69 6e 74 20 4e 32 2c 20 69 6e 74 20 nt, int N2, int
0760: 4e 33 2c 20 69 6e 74 20 4e 34 2c 20 63 6f 6e 73 N3, int N4, cons
0770: 74 20 54 26 20 74 20 3d 20 54 28 29 29 0a 09 09 t T& t = T())...
0780: 3a 20 4e 31 28 32 29 2c 20 4e 32 28 4e 32 29 2c : N1(2), N2(N2),
0790: 20 4e 33 28 4e 33 29 2c 20 4e 34 28 4e 34 29 2c N3(N3), N4(N4),
07a0: 20 64 61 74 61 28 4e 31 2a 4e 32 2a 4e 33 2a 4e data(N1*N2*N3*N
07b0: 34 2c 20 74 29 20 7b 20 61 73 73 65 72 74 28 64 4, t) { assert(d
07c0: 61 74 61 2e 73 69 7a 65 28 29 2a 73 69 7a 65 6f ata.size()*sizeo
07d0: 66 28 54 29 3c 28 31 3c 3c 32 36 29 29 3b 20 7d f(T)<(1<<26)); }
07e0: 0a 09 54 26 20 6f 70 65 72 61 74 6f 72 28 29 28 ..T& operator()(
07f0: 69 6e 74 20 69 31 2c 20 69 6e 74 20 69 32 2c 20 int i1, int i2,
0800: 69 6e 74 20 69 33 2c 20 69 6e 74 20 69 34 29 0a int i3, int i4).
0810: 09 09 7b 20 69 31 26 3d 31 3b 20 72 65 74 75 72 ..{ i1&=1; retur
0820: 6e 20 64 61 74 61 5b 20 28 28 28 69 31 2a 4e 32 n data[ (((i1*N2
0830: 29 2b 69 32 29 2a 4e 33 2b 69 33 29 2a 4e 34 2b )+i2)*N3+i3)*N4+
0840: 69 34 20 5d 3b 20 7d 0a 09 76 6f 69 64 20 73 77 i4 ]; }..void sw
0850: 61 70 28 44 50 34 78 26 20 72 68 73 29 0a 09 09 ap(DP4x& rhs)...
0860: 7b 20 64 61 74 61 2e 73 77 61 70 28 72 68 73 2e { data.swap(rhs.
0870: 64 61 74 61 29 3b 20 7d 0a 7d 3b 0a 0a 0a 2f 2f data); }.};...//
0880: 20 54 65 73 74 65 64 3a 20 53 52 4d 20 33 35 31 Tested: SRM 351
0890: 20 4c 76 32 0a 74 65 6d 70 6c 61 74 65 3c 74 79 Lv2.template<ty
08a0: 70 65 6e 61 6d 65 20 54 3e 0a 73 74 72 75 63 74 pename T>.struct
08b0: 20 44 50 35 0a 7b 0a 09 69 6e 74 20 4e 31 2c 20 DP5.{..int N1,
08c0: 4e 32 2c 20 4e 33 2c 20 4e 34 2c 20 4e 35 3b 0a N2, N3, N4, N5;.
08d0: 09 76 65 63 74 6f 72 3c 54 3e 20 64 61 74 61 3b .vector<T> data;
08e0: 0a 09 44 50 35 28 69 6e 74 20 4e 31 2c 20 69 6e ..DP5(int N1, in
08f0: 74 20 4e 32 2c 20 69 6e 74 20 4e 33 2c 20 69 6e t N2, int N3, in
0900: 74 20 4e 34 2c 20 69 6e 74 20 4e 35 2c 20 63 6f t N4, int N5, co
0910: 6e 73 74 20 54 26 20 74 20 3d 20 54 28 29 29 0a nst T& t = T()).
0920: 09 09 3a 20 4e 31 28 4e 31 29 2c 20 4e 32 28 4e ..: N1(N1), N2(N
0930: 32 29 2c 20 4e 33 28 4e 33 29 2c 20 4e 34 28 4e 2), N3(N3), N4(N
0940: 34 29 2c 20 4e 35 28 4e 35 29 2c 20 64 61 74 61 4), N5(N5), data
0950: 28 4e 31 2a 4e 32 2a 4e 33 2a 4e 34 2a 4e 35 2c (N1*N2*N3*N4*N5,
0960: 20 74 29 20 7b 20 61 73 73 65 72 74 28 64 61 74 t) { assert(dat
0970: 61 2e 73 69 7a 65 28 29 2a 73 69 7a 65 6f 66 28 a.size()*sizeof(
0980: 54 29 3c 28 31 3c 3c 32 36 29 29 3b 20 7d 0a 09 T)<(1<<26)); }..
0990: 54 26 20 6f 70 65 72 61 74 6f 72 28 29 28 69 6e T& operator()(in
09a0: 74 20 69 31 2c 20 69 6e 74 20 69 32 2c 20 69 6e t i1, int i2, in
09b0: 74 20 69 33 2c 20 69 6e 74 20 69 34 2c 20 69 6e t i3, int i4, in
09c0: 74 20 69 35 29 0a 09 09 7b 20 72 65 74 75 72 6e t i5)...{ return
09d0: 20 64 61 74 61 5b 20 28 28 28 28 69 31 2a 4e 32 data[ ((((i1*N2
09e0: 29 2b 69 32 29 2a 4e 33 2b 69 33 29 2a 4e 34 2b )+i2)*N3+i3)*N4+
09f0: 69 34 29 2a 4e 35 2b 69 35 20 5d 3b 20 7d 0a 09 i4)*N5+i5 ]; }..
0a00: 76 6f 69 64 20 73 77 61 70 28 44 50 35 26 20 72 void swap(DP5& r
0a10: 68 73 29 0a 09 09 7b 20 64 61 74 61 2e 73 77 61 hs)...{ data.swa
0a20: 70 28 72 68 73 2e 64 61 74 61 29 3b 20 7d 0a 7d p(rhs.data); }.}
0a30: 3b 0a 0a 2f 2f 20 4e 6f 74 20 54 65 73 74 65 64 ;..// Not Tested
0a40: 0a 74 65 6d 70 6c 61 74 65 3c 74 79 70 65 6e 61 .template<typena
0a50: 6d 65 20 54 3e 0a 73 74 72 75 63 74 20 44 50 35 me T>.struct DP5
0a60: 78 0a 7b 0a 09 69 6e 74 20 4e 31 2c 20 4e 32 2c x.{..int N1, N2,
0a70: 20 4e 33 2c 20 4e 34 2c 20 4e 35 3b 0a 09 76 65 N3, N4, N5;..ve
0a80: 63 74 6f 72 3c 54 3e 20 64 61 74 61 3b 0a 09 44 ctor<T> data;..D
0a90: 50 35 78 28 69 6e 74 2c 20 69 6e 74 20 4e 32 2c P5x(int, int N2,
0aa0: 20 69 6e 74 20 4e 33 2c 20 69 6e 74 20 4e 34 2c int N3, int N4,
0ab0: 20 69 6e 74 20 4e 35 2c 20 63 6f 6e 73 74 20 54 int N5, const T
0ac0: 26 20 74 20 3d 20 54 28 29 29 0a 09 09 3a 20 4e & t = T())...: N
0ad0: 31 28 32 29 2c 20 4e 32 28 4e 32 29 2c 20 4e 33 1(2), N2(N2), N3
0ae0: 28 4e 33 29 2c 20 4e 34 28 4e 34 29 2c 20 4e 35 (N3), N4(N4), N5
0af0: 28 4e 35 29 2c 20 64 61 74 61 28 4e 31 2a 4e 32 (N5), data(N1*N2
0b00: 2a 4e 33 2a 4e 34 2a 4e 35 2c 20 74 29 20 7b 20 *N3*N4*N5, t) {
0b10: 61 73 73 65 72 74 28 64 61 74 61 2e 73 69 7a 65 assert(data.size
0b20: 28 29 2a 73 69 7a 65 6f 66 28 54 29 3c 28 31 3c ()*sizeof(T)<(1<
0b30: 3c 32 36 29 29 3b 20 7d 0a 09 54 26 20 6f 70 65 <26)); }..T& ope
0b40: 72 61 74 6f 72 28 29 28 69 6e 74 20 69 31 2c 20 rator()(int i1,
0b50: 69 6e 74 20 69 32 2c 20 69 6e 74 20 69 33 2c 20 int i2, int i3,
0b60: 69 6e 74 20 69 34 2c 20 69 6e 74 20 69 35 29 0a int i4, int i5).
0b70: 09 09 7b 20 69 31 26 3d 31 3b 20 72 65 74 75 72 ..{ i1&=1; retur
0b80: 6e 20 64 61 74 61 5b 20 28 28 28 28 69 31 2a 4e n data[ ((((i1*N
0b90: 32 29 2b 69 32 29 2a 4e 33 2b 69 33 29 2a 4e 34 2)+i2)*N3+i3)*N4
0ba0: 2b 69 34 29 2a 4e 35 2b 69 35 20 5d 3b 20 7d 0a +i4)*N5+i5 ]; }.
0bb0: 09 76 6f 69 64 20 73 77 61 70 28 44 50 35 78 26 .void swap(DP5x&
0bc0: 20 72 68 73 29 0a 09 09 7b 20 64 61 74 61 2e 73 rhs)...{ data.s
0bd0: 77 61 70 28 72 68 73 2e 64 61 74 61 29 3b 20 7d wap(rhs.data); }
0be0: 0a 7d 3b 0a .};.