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 38 29 29 3b 20 of(T)<(1<<28));
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 2c 20 53 52 4d 20 35 32 38 20 4c 76 32 0a 74 C, SRM 528 Lv2.t
0170: 65 6d 70 6c 61 74 65 3c 74 79 70 65 6e 61 6d 65 emplate<typename
0180: 20 54 3e 0a 73 74 72 75 63 74 20 44 50 32 78 0a T>.struct DP2x.
0190: 7b 0a 09 63 6f 6e 73 74 20 69 6e 74 20 4e 31 2c {..const int N1,
01a0: 20 4e 32 3b 0a 09 76 65 63 74 6f 72 3c 54 3e 20 N2;..vector<T>
01b0: 64 61 74 61 3b 0a 09 44 50 32 78 28 69 6e 74 2c data;..DP2x(int,
01c0: 20 69 6e 74 20 4e 32 2c 20 63 6f 6e 73 74 20 54 int N2, const T
01d0: 26 20 74 20 3d 20 54 28 29 29 0a 09 09 3a 20 4e & t = T())...: N
01e0: 31 28 32 29 2c 20 4e 32 28 4e 32 29 2c 20 64 61 1(2), N2(N2), da
01f0: 74 61 28 4e 31 2a 4e 32 2c 20 74 29 20 7b 20 61 ta(N1*N2, t) { a
0200: 73 73 65 72 74 28 64 61 74 61 2e 73 69 7a 65 28 ssert(data.size(
0210: 29 2a 73 69 7a 65 6f 66 28 54 29 3c 28 31 3c 3c )*sizeof(T)<(1<<
0220: 32 38 29 29 3b 20 7d 0a 09 54 26 20 6f 70 65 72 28)); }..T& oper
0230: 61 74 6f 72 28 29 28 69 6e 74 20 69 31 2c 20 69 ator()(int i1, i
0240: 6e 74 20 69 32 29 0a 09 09 7b 20 69 31 26 3d 31 nt i2)...{ i1&=1
0250: 3b 20 72 65 74 75 72 6e 20 64 61 74 61 5b 20 28 ; return data[ (
0260: 69 31 2a 4e 32 29 2b 69 32 20 5d 3b 20 7d 0a 09 i1*N2)+i2 ]; }..
0270: 76 6f 69 64 20 73 77 61 70 28 44 50 32 78 26 20 void swap(DP2x&
0280: 72 68 73 29 0a 09 09 7b 20 64 61 74 61 2e 73 77 rhs)...{ data.sw
0290: 61 70 28 72 68 73 2e 64 61 74 61 29 3b 20 7d 0a ap(rhs.data); }.
02a0: 7d 3b 0a 0a 2f 2f 20 54 65 73 74 65 64 3a 20 53 };..// Tested: S
02b0: 52 4d 20 34 35 32 20 4c 76 33 0a 74 65 6d 70 6c RM 452 Lv3.templ
02c0: 61 74 65 3c 74 79 70 65 6e 61 6d 65 20 54 3e 0a ate<typename T>.
02d0: 73 74 72 75 63 74 20 44 50 33 0a 7b 0a 09 69 6e struct DP3.{..in
02e0: 74 20 4e 31 2c 20 4e 32 2c 20 4e 33 3b 0a 09 76 t N1, N2, N3;..v
02f0: 65 63 74 6f 72 3c 54 3e 20 64 61 74 61 3b 0a 09 ector<T> data;..
0300: 44 50 33 28 69 6e 74 20 4e 31 2c 20 69 6e 74 20 DP3(int N1, int
0310: 4e 32 2c 20 69 6e 74 20 4e 33 2c 20 63 6f 6e 73 N2, int N3, cons
0320: 74 20 54 26 20 74 20 3d 20 54 28 29 29 0a 09 09 t T& t = T())...
0330: 3a 20 4e 31 28 4e 31 29 2c 20 4e 32 28 4e 32 29 : N1(N1), N2(N2)
0340: 2c 20 4e 33 28 4e 33 29 2c 20 64 61 74 61 28 4e , N3(N3), data(N
0350: 31 2a 4e 32 2a 4e 33 2c 20 74 29 20 7b 20 61 73 1*N2*N3, t) { as
0360: 73 65 72 74 28 64 61 74 61 2e 73 69 7a 65 28 29 sert(data.size()
0370: 2a 73 69 7a 65 6f 66 28 54 29 3c 28 31 3c 3c 32 *sizeof(T)<(1<<2
0380: 38 29 29 3b 20 7d 0a 09 54 26 20 6f 70 65 72 61 8)); }..T& opera
0390: 74 6f 72 28 29 28 69 6e 74 20 69 31 2c 20 69 6e tor()(int i1, in
03a0: 74 20 69 32 2c 20 69 6e 74 20 69 33 29 0a 09 09 t i2, int i3)...
03b0: 7b 20 72 65 74 75 72 6e 20 64 61 74 61 5b 20 28 { return data[ (
03c0: 28 69 31 2a 4e 32 29 2b 69 32 29 2a 4e 33 2b 69 (i1*N2)+i2)*N3+i
03d0: 33 20 5d 3b 20 7d 0a 09 76 6f 69 64 20 73 77 61 3 ]; }..void swa
03e0: 70 28 44 50 33 26 20 72 68 73 29 0a 09 09 7b 20 p(DP3& rhs)...{
03f0: 64 61 74 61 2e 73 77 61 70 28 72 68 73 2e 64 61 data.swap(rhs.da
0400: 74 61 29 3b 20 7d 0a 7d 3b 0a 0a 2f 2f 20 54 65 ta); }.};..// Te
0410: 73 74 65 64 3a 20 53 52 4d 20 34 36 38 20 4c 76 sted: SRM 468 Lv
0420: 32 0a 74 65 6d 70 6c 61 74 65 3c 74 79 70 65 6e 2.template<typen
0430: 61 6d 65 20 54 3e 0a 73 74 72 75 63 74 20 44 50 ame T>.struct DP
0440: 33 78 0a 7b 0a 09 69 6e 74 20 4e 31 2c 20 4e 32 3x.{..int N1, N2
0450: 2c 20 4e 33 3b 0a 09 76 65 63 74 6f 72 3c 54 3e , N3;..vector<T>
0460: 20 64 61 74 61 3b 0a 09 44 50 33 78 28 69 6e 74 data;..DP3x(int
0470: 2c 20 69 6e 74 20 4e 32 2c 20 69 6e 74 20 4e 33 , int N2, int N3
0480: 2c 20 63 6f 6e 73 74 20 54 26 20 74 20 3d 20 54 , const T& t = T
0490: 28 29 29 0a 09 09 3a 20 4e 31 28 32 29 2c 20 4e ())...: N1(2), N
04a0: 32 28 4e 32 29 2c 20 4e 33 28 4e 33 29 2c 20 64 2(N2), N3(N3), d
04b0: 61 74 61 28 4e 31 2a 4e 32 2a 4e 33 2c 20 74 29 ata(N1*N2*N3, t)
04c0: 20 7b 20 61 73 73 65 72 74 28 64 61 74 61 2e 73 { assert(data.s
04d0: 69 7a 65 28 29 2a 73 69 7a 65 6f 66 28 54 29 20 ize()*sizeof(T)
04e0: 3c 20 28 31 3c 3c 32 38 29 29 3b 20 7d 0a 09 54 < (1<<28)); }..T
04f0: 26 20 6f 70 65 72 61 74 6f 72 28 29 28 69 6e 74 & operator()(int
0500: 20 69 31 2c 20 69 6e 74 20 69 32 2c 20 69 6e 74 i1, int i2, int
0510: 20 69 33 29 0a 09 09 7b 20 69 31 26 3d 31 3b 20 i3)...{ i1&=1;
0520: 72 65 74 75 72 6e 20 64 61 74 61 5b 20 28 28 69 return data[ ((i
0530: 31 2a 4e 32 29 2b 69 32 29 2a 4e 33 2b 69 33 20 1*N2)+i2)*N3+i3
0540: 5d 3b 20 7d 0a 09 76 6f 69 64 20 73 77 61 70 28 ]; }..void swap(
0550: 44 50 33 78 26 20 72 68 73 29 0a 09 09 7b 20 64 DP3x& rhs)...{ d
0560: 61 74 61 2e 73 77 61 70 28 72 68 73 2e 64 61 74 ata.swap(rhs.dat
0570: 61 29 3b 20 7d 0a 7d 3b 0a 0a 2f 2f 20 54 65 73 a); }.};..// Tes
0580: 74 65 64 3a 20 53 52 4d 20 35 32 30 20 4c 76 32 ted: SRM 520 Lv2
0590: 0a 74 65 6d 70 6c 61 74 65 3c 74 79 70 65 6e 61 .template<typena
05a0: 6d 65 20 54 3e 0a 73 74 72 75 63 74 20 44 50 34 me T>.struct DP4
05b0: 0a 7b 0a 09 69 6e 74 20 4e 31 2c 20 4e 32 2c 20 .{..int N1, N2,
05c0: 4e 33 2c 20 4e 34 3b 0a 09 76 65 63 74 6f 72 3c N3, N4;..vector<
05d0: 54 3e 20 64 61 74 61 3b 0a 09 44 50 34 28 69 6e T> data;..DP4(in
05e0: 74 20 4e 31 2c 20 69 6e 74 20 4e 32 2c 20 69 6e t N1, int N2, in
05f0: 74 20 4e 33 2c 20 69 6e 74 20 4e 34 2c 20 63 6f t N3, int N4, co
0600: 6e 73 74 20 54 26 20 74 20 3d 20 54 28 29 29 0a nst T& t = T()).
0610: 09 09 3a 20 4e 31 28 4e 31 29 2c 20 4e 32 28 4e ..: N1(N1), N2(N
0620: 32 29 2c 20 4e 33 28 4e 33 29 2c 20 4e 34 28 4e 2), N3(N3), N4(N
0630: 34 29 2c 20 64 61 74 61 28 4e 31 2a 4e 32 2a 4e 4), data(N1*N2*N
0640: 33 2a 4e 34 2c 20 74 29 20 7b 20 61 73 73 65 72 3*N4, t) { asser
0650: 74 28 64 61 74 61 2e 73 69 7a 65 28 29 2a 73 69 t(data.size()*si
0660: 7a 65 6f 66 28 54 29 3c 28 31 3c 3c 32 38 29 29 zeof(T)<(1<<28))
0670: 3b 20 7d 0a 09 54 26 20 6f 70 65 72 61 74 6f 72 ; }..T& operator
0680: 28 29 28 69 6e 74 20 69 31 2c 20 69 6e 74 20 69 ()(int i1, int i
0690: 32 2c 20 69 6e 74 20 69 33 2c 20 69 6e 74 20 69 2, int i3, int i
06a0: 34 29 0a 09 09 7b 20 72 65 74 75 72 6e 20 64 61 4)...{ return da
06b0: 74 61 5b 20 28 28 28 69 31 2a 4e 32 29 2b 69 32 ta[ (((i1*N2)+i2
06c0: 29 2a 4e 33 2b 69 33 29 2a 4e 34 2b 69 34 20 5d )*N3+i3)*N4+i4 ]
06d0: 3b 20 7d 0a 09 76 6f 69 64 20 73 77 61 70 28 44 ; }..void swap(D
06e0: 50 34 26 20 72 68 73 29 0a 09 09 7b 20 64 61 74 P4& rhs)...{ dat
06f0: 61 2e 73 77 61 70 28 72 68 73 2e 64 61 74 61 29 a.swap(rhs.data)
0700: 3b 20 7d 0a 7d 3b 0a 0a 2f 2f 20 4e 6f 74 20 54 ; }.};..// Not T
0710: 65 73 74 65 64 0a 74 65 6d 70 6c 61 74 65 3c 74 ested.template<t
0720: 79 70 65 6e 61 6d 65 20 54 3e 0a 73 74 72 75 63 ypename T>.struc
0730: 74 20 44 50 34 78 0a 7b 0a 09 69 6e 74 20 4e 31 t DP4x.{..int N1
0740: 2c 20 4e 32 2c 20 4e 33 2c 20 4e 34 3b 0a 09 76 , N2, N3, N4;..v
0750: 65 63 74 6f 72 3c 54 3e 20 64 61 74 61 3b 0a 09 ector<T> data;..
0760: 44 50 34 78 28 69 6e 74 2c 20 69 6e 74 20 4e 32 DP4x(int, int N2
0770: 2c 20 69 6e 74 20 4e 33 2c 20 69 6e 74 20 4e 34 , int N3, int N4
0780: 2c 20 63 6f 6e 73 74 20 54 26 20 74 20 3d 20 54 , const T& t = T
0790: 28 29 29 0a 09 09 3a 20 4e 31 28 32 29 2c 20 4e ())...: N1(2), N
07a0: 32 28 4e 32 29 2c 20 4e 33 28 4e 33 29 2c 20 4e 2(N2), N3(N3), N
07b0: 34 28 4e 34 29 2c 20 64 61 74 61 28 4e 31 2a 4e 4(N4), data(N1*N
07c0: 32 2a 4e 33 2a 4e 34 2c 20 74 29 20 7b 20 61 73 2*N3*N4, t) { as
07d0: 73 65 72 74 28 64 61 74 61 2e 73 69 7a 65 28 29 sert(data.size()
07e0: 2a 73 69 7a 65 6f 66 28 54 29 3c 28 31 3c 3c 32 *sizeof(T)<(1<<2
07f0: 38 29 29 3b 20 7d 0a 09 54 26 20 6f 70 65 72 61 8)); }..T& opera
0800: 74 6f 72 28 29 28 69 6e 74 20 69 31 2c 20 69 6e tor()(int i1, in
0810: 74 20 69 32 2c 20 69 6e 74 20 69 33 2c 20 69 6e t i2, int i3, in
0820: 74 20 69 34 29 0a 09 09 7b 20 69 31 26 3d 31 3b t i4)...{ i1&=1;
0830: 20 72 65 74 75 72 6e 20 64 61 74 61 5b 20 28 28 return data[ ((
0840: 28 69 31 2a 4e 32 29 2b 69 32 29 2a 4e 33 2b 69 (i1*N2)+i2)*N3+i
0850: 33 29 2a 4e 34 2b 69 34 20 5d 3b 20 7d 0a 09 76 3)*N4+i4 ]; }..v
0860: 6f 69 64 20 73 77 61 70 28 44 50 34 78 26 20 72 oid swap(DP4x& r
0870: 68 73 29 0a 09 09 7b 20 64 61 74 61 2e 73 77 61 hs)...{ data.swa
0880: 70 28 72 68 73 2e 64 61 74 61 29 3b 20 7d 0a 7d p(rhs.data); }.}
0890: 3b 0a 0a 0a 2f 2f 20 54 65 73 74 65 64 3a 20 53 ;...// Tested: S
08a0: 52 4d 20 33 35 31 20 4c 76 32 0a 74 65 6d 70 6c RM 351 Lv2.templ
08b0: 61 74 65 3c 74 79 70 65 6e 61 6d 65 20 54 3e 0a ate<typename T>.
08c0: 73 74 72 75 63 74 20 44 50 35 0a 7b 0a 09 69 6e struct DP5.{..in
08d0: 74 20 4e 31 2c 20 4e 32 2c 20 4e 33 2c 20 4e 34 t N1, N2, N3, N4
08e0: 2c 20 4e 35 3b 0a 09 76 65 63 74 6f 72 3c 54 3e , N5;..vector<T>
08f0: 20 64 61 74 61 3b 0a 09 44 50 35 28 69 6e 74 20 data;..DP5(int
0900: 4e 31 2c 20 69 6e 74 20 4e 32 2c 20 69 6e 74 20 N1, int N2, int
0910: 4e 33 2c 20 69 6e 74 20 4e 34 2c 20 69 6e 74 20 N3, int N4, int
0920: 4e 35 2c 20 63 6f 6e 73 74 20 54 26 20 74 20 3d N5, const T& t =
0930: 20 54 28 29 29 0a 09 09 3a 20 4e 31 28 4e 31 29 T())...: N1(N1)
0940: 2c 20 4e 32 28 4e 32 29 2c 20 4e 33 28 4e 33 29 , N2(N2), N3(N3)
0950: 2c 20 4e 34 28 4e 34 29 2c 20 4e 35 28 4e 35 29 , N4(N4), N5(N5)
0960: 2c 20 64 61 74 61 28 4e 31 2a 4e 32 2a 4e 33 2a , data(N1*N2*N3*
0970: 4e 34 2a 4e 35 2c 20 74 29 20 7b 20 61 73 73 65 N4*N5, t) { asse
0980: 72 74 28 64 61 74 61 2e 73 69 7a 65 28 29 2a 73 rt(data.size()*s
0990: 69 7a 65 6f 66 28 54 29 3c 28 31 3c 3c 32 38 29 izeof(T)<(1<<28)
09a0: 29 3b 20 7d 0a 09 54 26 20 6f 70 65 72 61 74 6f ); }..T& operato
09b0: 72 28 29 28 69 6e 74 20 69 31 2c 20 69 6e 74 20 r()(int i1, int
09c0: 69 32 2c 20 69 6e 74 20 69 33 2c 20 69 6e 74 20 i2, int i3, int
09d0: 69 34 2c 20 69 6e 74 20 69 35 29 0a 09 09 7b 20 i4, int i5)...{
09e0: 72 65 74 75 72 6e 20 64 61 74 61 5b 20 28 28 28 return data[ (((
09f0: 28 69 31 2a 4e 32 29 2b 69 32 29 2a 4e 33 2b 69 (i1*N2)+i2)*N3+i
0a00: 33 29 2a 4e 34 2b 69 34 29 2a 4e 35 2b 69 35 20 3)*N4+i4)*N5+i5
0a10: 5d 3b 20 7d 0a 09 76 6f 69 64 20 73 77 61 70 28 ]; }..void swap(
0a20: 44 50 35 26 20 72 68 73 29 0a 09 09 7b 20 64 61 DP5& rhs)...{ da
0a30: 74 61 2e 73 77 61 70 28 72 68 73 2e 64 61 74 61 ta.swap(rhs.data
0a40: 29 3b 20 7d 0a 7d 3b 0a 0a 2f 2f 20 4e 6f 74 20 ); }.};..// Not
0a50: 54 65 73 74 65 64 0a 74 65 6d 70 6c 61 74 65 3c Tested.template<
0a60: 74 79 70 65 6e 61 6d 65 20 54 3e 0a 73 74 72 75 typename T>.stru
0a70: 63 74 20 44 50 35 78 0a 7b 0a 09 69 6e 74 20 4e ct DP5x.{..int N
0a80: 31 2c 20 4e 32 2c 20 4e 33 2c 20 4e 34 2c 20 4e 1, N2, N3, N4, N
0a90: 35 3b 0a 09 76 65 63 74 6f 72 3c 54 3e 20 64 61 5;..vector<T> da
0aa0: 74 61 3b 0a 09 44 50 35 78 28 69 6e 74 2c 20 69 ta;..DP5x(int, i
0ab0: 6e 74 20 4e 32 2c 20 69 6e 74 20 4e 33 2c 20 69 nt N2, int N3, i
0ac0: 6e 74 20 4e 34 2c 20 69 6e 74 20 4e 35 2c 20 63 nt N4, int N5, c
0ad0: 6f 6e 73 74 20 54 26 20 74 20 3d 20 54 28 29 29 onst T& t = T())
0ae0: 0a 09 09 3a 20 4e 31 28 32 29 2c 20 4e 32 28 4e ...: N1(2), N2(N
0af0: 32 29 2c 20 4e 33 28 4e 33 29 2c 20 4e 34 28 4e 2), N3(N3), N4(N
0b00: 34 29 2c 20 4e 35 28 4e 35 29 2c 20 64 61 74 61 4), N5(N5), data
0b10: 28 4e 31 2a 4e 32 2a 4e 33 2a 4e 34 2a 4e 35 2c (N1*N2*N3*N4*N5,
0b20: 20 74 29 20 7b 20 61 73 73 65 72 74 28 64 61 74 t) { assert(dat
0b30: 61 2e 73 69 7a 65 28 29 2a 73 69 7a 65 6f 66 28 a.size()*sizeof(
0b40: 54 29 3c 28 31 3c 3c 32 38 29 29 3b 20 7d 0a 09 T)<(1<<28)); }..
0b50: 54 26 20 6f 70 65 72 61 74 6f 72 28 29 28 69 6e T& operator()(in
0b60: 74 20 69 31 2c 20 69 6e 74 20 69 32 2c 20 69 6e t i1, int i2, in
0b70: 74 20 69 33 2c 20 69 6e 74 20 69 34 2c 20 69 6e t i3, int i4, in
0b80: 74 20 69 35 29 0a 09 09 7b 20 69 31 26 3d 31 3b t i5)...{ i1&=1;
0b90: 20 72 65 74 75 72 6e 20 64 61 74 61 5b 20 28 28 return data[ ((
0ba0: 28 28 69 31 2a 4e 32 29 2b 69 32 29 2a 4e 33 2b ((i1*N2)+i2)*N3+
0bb0: 69 33 29 2a 4e 34 2b 69 34 29 2a 4e 35 2b 69 35 i3)*N4+i4)*N5+i5
0bc0: 20 5d 3b 20 7d 0a 09 76 6f 69 64 20 73 77 61 70 ]; }..void swap
0bd0: 28 44 50 35 78 26 20 72 68 73 29 0a 09 09 7b 20 (DP5x& rhs)...{
0be0: 64 61 74 61 2e 73 77 61 70 28 72 68 73 2e 64 61 data.swap(rhs.da
0bf0: 74 61 29 3b 20 7d 0a 7d 3b 0a ta); }.};.