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: 54 65 73 74 65 64 3a 20 53 52 4d 20 35 32 30 20 Tested: SRM 520
0580: 4c 76 32 0a 74 65 6d 70 6c 61 74 65 3c 74 79 70 Lv2.template<typ
0590: 65 6e 61 6d 65 20 54 3e 0a 73 74 72 75 63 74 20 ename T>.struct
05a0: 44 50 34 0a 7b 0a 09 69 6e 74 20 4e 31 2c 20 4e DP4.{..int N1, N
05b0: 32 2c 20 4e 33 2c 20 4e 34 3b 0a 09 76 65 63 74 2, N3, N4;..vect
05c0: 6f 72 3c 54 3e 20 64 61 74 61 3b 0a 09 44 50 34 or<T> data;..DP4
05d0: 28 69 6e 74 20 4e 31 2c 20 69 6e 74 20 4e 32 2c (int N1, int N2,
05e0: 20 69 6e 74 20 4e 33 2c 20 69 6e 74 20 4e 34 2c int N3, int N4,
05f0: 20 63 6f 6e 73 74 20 54 26 20 74 20 3d 20 54 28 const T& t = T(
0600: 29 29 0a 09 09 3a 20 4e 31 28 4e 31 29 2c 20 4e ))...: N1(N1), N
0610: 32 28 4e 32 29 2c 20 4e 33 28 4e 33 29 2c 20 4e 2(N2), N3(N3), N
0620: 34 28 4e 34 29 2c 20 64 61 74 61 28 4e 31 2a 4e 4(N4), data(N1*N
0630: 32 2a 4e 33 2a 4e 34 2c 20 74 29 20 7b 20 61 73 2*N3*N4, t) { as
0640: 73 65 72 74 28 64 61 74 61 2e 73 69 7a 65 28 29 sert(data.size()
0650: 2a 73 69 7a 65 6f 66 28 54 29 3c 28 31 3c 3c 32 *sizeof(T)<(1<<2
0660: 36 29 29 3b 20 7d 0a 09 54 26 20 6f 70 65 72 61 6)); }..T& opera
0670: 74 6f 72 28 29 28 69 6e 74 20 69 31 2c 20 69 6e tor()(int i1, in
0680: 74 20 69 32 2c 20 69 6e 74 20 69 33 2c 20 69 6e t i2, int i3, in
0690: 74 20 69 34 29 0a 09 09 7b 20 72 65 74 75 72 6e t i4)...{ return
06a0: 20 64 61 74 61 5b 20 28 28 28 69 31 2a 4e 32 29 data[ (((i1*N2)
06b0: 2b 69 32 29 2a 4e 33 2b 69 33 29 2a 4e 34 2b 69 +i2)*N3+i3)*N4+i
06c0: 34 20 5d 3b 20 7d 0a 09 76 6f 69 64 20 73 77 61 4 ]; }..void swa
06d0: 70 28 44 50 34 26 20 72 68 73 29 0a 09 09 7b 20 p(DP4& rhs)...{
06e0: 64 61 74 61 2e 73 77 61 70 28 72 68 73 2e 64 61 data.swap(rhs.da
06f0: 74 61 29 3b 20 7d 0a 7d 3b 0a 0a 2f 2f 20 4e 6f ta); }.};..// No
0700: 74 20 54 65 73 74 65 64 0a 74 65 6d 70 6c 61 74 t Tested.templat
0710: 65 3c 74 79 70 65 6e 61 6d 65 20 54 3e 0a 73 74 e<typename T>.st
0720: 72 75 63 74 20 44 50 34 78 0a 7b 0a 09 69 6e 74 ruct DP4x.{..int
0730: 20 4e 31 2c 20 4e 32 2c 20 4e 33 2c 20 4e 34 3b N1, N2, N3, N4;
0740: 0a 09 76 65 63 74 6f 72 3c 54 3e 20 64 61 74 61 ..vector<T> data
0750: 3b 0a 09 44 50 34 78 28 69 6e 74 2c 20 69 6e 74 ;..DP4x(int, int
0760: 20 4e 32 2c 20 69 6e 74 20 4e 33 2c 20 69 6e 74 N2, int N3, int
0770: 20 4e 34 2c 20 63 6f 6e 73 74 20 54 26 20 74 20 N4, const T& t
0780: 3d 20 54 28 29 29 0a 09 09 3a 20 4e 31 28 32 29 = T())...: N1(2)
0790: 2c 20 4e 32 28 4e 32 29 2c 20 4e 33 28 4e 33 29 , N2(N2), N3(N3)
07a0: 2c 20 4e 34 28 4e 34 29 2c 20 64 61 74 61 28 4e , N4(N4), data(N
07b0: 31 2a 4e 32 2a 4e 33 2a 4e 34 2c 20 74 29 20 7b 1*N2*N3*N4, t) {
07c0: 20 61 73 73 65 72 74 28 64 61 74 61 2e 73 69 7a assert(data.siz
07d0: 65 28 29 2a 73 69 7a 65 6f 66 28 54 29 3c 28 31 e()*sizeof(T)<(1
07e0: 3c 3c 32 36 29 29 3b 20 7d 0a 09 54 26 20 6f 70 <<26)); }..T& op
07f0: 65 72 61 74 6f 72 28 29 28 69 6e 74 20 69 31 2c erator()(int i1,
0800: 20 69 6e 74 20 69 32 2c 20 69 6e 74 20 69 33 2c int i2, int i3,
0810: 20 69 6e 74 20 69 34 29 0a 09 09 7b 20 69 31 26 int i4)...{ i1&
0820: 3d 31 3b 20 72 65 74 75 72 6e 20 64 61 74 61 5b =1; return data[
0830: 20 28 28 28 69 31 2a 4e 32 29 2b 69 32 29 2a 4e (((i1*N2)+i2)*N
0840: 33 2b 69 33 29 2a 4e 34 2b 69 34 20 5d 3b 20 7d 3+i3)*N4+i4 ]; }
0850: 0a 09 76 6f 69 64 20 73 77 61 70 28 44 50 34 78 ..void swap(DP4x
0860: 26 20 72 68 73 29 0a 09 09 7b 20 64 61 74 61 2e & rhs)...{ data.
0870: 73 77 61 70 28 72 68 73 2e 64 61 74 61 29 3b 20 swap(rhs.data);
0880: 7d 0a 7d 3b 0a 0a 0a 2f 2f 20 54 65 73 74 65 64 }.};...// Tested
0890: 3a 20 53 52 4d 20 33 35 31 20 4c 76 32 0a 74 65 : SRM 351 Lv2.te
08a0: 6d 70 6c 61 74 65 3c 74 79 70 65 6e 61 6d 65 20 mplate<typename
08b0: 54 3e 0a 73 74 72 75 63 74 20 44 50 35 0a 7b 0a T>.struct DP5.{.
08c0: 09 69 6e 74 20 4e 31 2c 20 4e 32 2c 20 4e 33 2c .int N1, N2, N3,
08d0: 20 4e 34 2c 20 4e 35 3b 0a 09 76 65 63 74 6f 72 N4, N5;..vector
08e0: 3c 54 3e 20 64 61 74 61 3b 0a 09 44 50 35 28 69 <T> data;..DP5(i
08f0: 6e 74 20 4e 31 2c 20 69 6e 74 20 4e 32 2c 20 69 nt N1, int N2, i
0900: 6e 74 20 4e 33 2c 20 69 6e 74 20 4e 34 2c 20 69 nt N3, int N4, i
0910: 6e 74 20 4e 35 2c 20 63 6f 6e 73 74 20 54 26 20 nt N5, const T&
0920: 74 20 3d 20 54 28 29 29 0a 09 09 3a 20 4e 31 28 t = T())...: N1(
0930: 4e 31 29 2c 20 4e 32 28 4e 32 29 2c 20 4e 33 28 N1), N2(N2), N3(
0940: 4e 33 29 2c 20 4e 34 28 4e 34 29 2c 20 4e 35 28 N3), N4(N4), N5(
0950: 4e 35 29 2c 20 64 61 74 61 28 4e 31 2a 4e 32 2a N5), data(N1*N2*
0960: 4e 33 2a 4e 34 2a 4e 35 2c 20 74 29 20 7b 20 61 N3*N4*N5, t) { a
0970: 73 73 65 72 74 28 64 61 74 61 2e 73 69 7a 65 28 ssert(data.size(
0980: 29 2a 73 69 7a 65 6f 66 28 54 29 3c 28 31 3c 3c )*sizeof(T)<(1<<
0990: 32 36 29 29 3b 20 7d 0a 09 54 26 20 6f 70 65 72 26)); }..T& oper
09a0: 61 74 6f 72 28 29 28 69 6e 74 20 69 31 2c 20 69 ator()(int i1, i
09b0: 6e 74 20 69 32 2c 20 69 6e 74 20 69 33 2c 20 69 nt i2, int i3, i
09c0: 6e 74 20 69 34 2c 20 69 6e 74 20 69 35 29 0a 09 nt i4, int i5)..
09d0: 09 7b 20 72 65 74 75 72 6e 20 64 61 74 61 5b 20 .{ return data[
09e0: 28 28 28 28 69 31 2a 4e 32 29 2b 69 32 29 2a 4e ((((i1*N2)+i2)*N
09f0: 33 2b 69 33 29 2a 4e 34 2b 69 34 29 2a 4e 35 2b 3+i3)*N4+i4)*N5+
0a00: 69 35 20 5d 3b 20 7d 0a 09 76 6f 69 64 20 73 77 i5 ]; }..void sw
0a10: 61 70 28 44 50 35 26 20 72 68 73 29 0a 09 09 7b ap(DP5& rhs)...{
0a20: 20 64 61 74 61 2e 73 77 61 70 28 72 68 73 2e 64 data.swap(rhs.d
0a30: 61 74 61 29 3b 20 7d 0a 7d 3b 0a 0a 2f 2f 20 4e ata); }.};..// N
0a40: 6f 74 20 54 65 73 74 65 64 0a 74 65 6d 70 6c 61 ot Tested.templa
0a50: 74 65 3c 74 79 70 65 6e 61 6d 65 20 54 3e 0a 73 te<typename T>.s
0a60: 74 72 75 63 74 20 44 50 35 78 0a 7b 0a 09 69 6e truct DP5x.{..in
0a70: 74 20 4e 31 2c 20 4e 32 2c 20 4e 33 2c 20 4e 34 t N1, N2, N3, N4
0a80: 2c 20 4e 35 3b 0a 09 76 65 63 74 6f 72 3c 54 3e , N5;..vector<T>
0a90: 20 64 61 74 61 3b 0a 09 44 50 35 78 28 69 6e 74 data;..DP5x(int
0aa0: 2c 20 69 6e 74 20 4e 32 2c 20 69 6e 74 20 4e 33 , int N2, int N3
0ab0: 2c 20 69 6e 74 20 4e 34 2c 20 69 6e 74 20 4e 35 , int N4, int N5
0ac0: 2c 20 63 6f 6e 73 74 20 54 26 20 74 20 3d 20 54 , const T& t = T
0ad0: 28 29 29 0a 09 09 3a 20 4e 31 28 32 29 2c 20 4e ())...: N1(2), N
0ae0: 32 28 4e 32 29 2c 20 4e 33 28 4e 33 29 2c 20 4e 2(N2), N3(N3), N
0af0: 34 28 4e 34 29 2c 20 4e 35 28 4e 35 29 2c 20 64 4(N4), N5(N5), d
0b00: 61 74 61 28 4e 31 2a 4e 32 2a 4e 33 2a 4e 34 2a ata(N1*N2*N3*N4*
0b10: 4e 35 2c 20 74 29 20 7b 20 61 73 73 65 72 74 28 N5, t) { assert(
0b20: 64 61 74 61 2e 73 69 7a 65 28 29 2a 73 69 7a 65 data.size()*size
0b30: 6f 66 28 54 29 3c 28 31 3c 3c 32 36 29 29 3b 20 of(T)<(1<<26));
0b40: 7d 0a 09 54 26 20 6f 70 65 72 61 74 6f 72 28 29 }..T& operator()
0b50: 28 69 6e 74 20 69 31 2c 20 69 6e 74 20 69 32 2c (int i1, int i2,
0b60: 20 69 6e 74 20 69 33 2c 20 69 6e 74 20 69 34 2c int i3, int i4,
0b70: 20 69 6e 74 20 69 35 29 0a 09 09 7b 20 69 31 26 int i5)...{ i1&
0b80: 3d 31 3b 20 72 65 74 75 72 6e 20 64 61 74 61 5b =1; return data[
0b90: 20 28 28 28 28 69 31 2a 4e 32 29 2b 69 32 29 2a ((((i1*N2)+i2)*
0ba0: 4e 33 2b 69 33 29 2a 4e 34 2b 69 34 29 2a 4e 35 N3+i3)*N4+i4)*N5
0bb0: 2b 69 35 20 5d 3b 20 7d 0a 09 76 6f 69 64 20 73 +i5 ]; }..void s
0bc0: 77 61 70 28 44 50 35 78 26 20 72 68 73 29 0a 09 wap(DP5x& rhs)..
0bd0: 09 7b 20 64 61 74 61 2e 73 77 61 70 28 72 68 73 .{ data.swap(rhs
0be0: 2e 64 61 74 61 29 3b 20 7d 0a 7d 3b 0a .data); }.};.