Overview
| SHA1 Hash: | 3d2bcff745a0abb78103b30484d868d1706584e8 |
|---|---|
| Date: | 2011-12-29 06:57:30 |
| User: | kinaba |
| Comment: | 528 |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
Added SRM/528/1A.cpp version [1f7e5221dd3ee508]
> 1 #include <iostream> > 2 #include <sstream> > 3 #include <iomanip> > 4 #include <vector> > 5 #include <string> > 6 #include <map> > 7 #include <set> > 8 #include <algorithm> > 9 #include <numeric> > 10 #include <iterator> > 11 #include <functional> > 12 #include <complex> > 13 #include <queue> > 14 #include <stack> > 15 #include <cmath> > 16 #include <cassert> > 17 #include <cstring> > 18 #ifdef __GNUC__ > 19 #include <ext/hash_map> > 20 #define unordered_map __gnu_cxx::hash_map > 21 #else > 22 #include <unordered_map> > 23 #endif > 24 using namespace std; > 25 typedef long long LL; > 26 typedef complex<double> CMP; > 27 > 28 class Cut { public: > 29 static bool TensFirst(int a, int b) > 30 { > 31 if(a%10 != b%10) > 32 return a%10 < b%10; > 33 return a < b; > 34 } > 35 > 36 int getMaximum(vector <int> eelLengths, int maxCuts) > 37 { > 38 sort(eelLengths.begin(), eelLengths.end(), &TensFirst); > 39 > 40 int una = 0; > 41 for(int i=0; i<eelLengths.size(); ++i) { > 42 int e = eelLengths[i]; > 43 while( maxCuts && e>10 ) > 44 una++, maxCuts--, e-=10; > 45 if( e == 10 ) > 46 una++; > 47 } > 48 return una; > 49 } > 50 }; > 51 > 52 // BEGIN CUT HERE > 53 #include <ctime> > 54 double start_time; string timer() > 55 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 56 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 57 { os << "{ "; > 58 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 59 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 60 void verify_case(const int& Expected, const int& Received) { > 61 bool ok = (Expected == Received); > 62 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 63 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 64 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 65 #define END verify_case(_, Cut().getMaximum(eelLengths, maxCuts));} > 66 int main(){ > 67 > 68 CASE(0) > 69 int eelLengths_[] = {13, 20, 13}; > 70 vector <int> eelLengths(eelLengths_, eelLengths_+sizeof(eelLengths_)/s > 71 int maxCuts = 2; > 72 int _ = 3; > 73 END > 74 CASE(1) > 75 int eelLengths_[] = {5, 5, 5, 5}; > 76 vector <int> eelLengths(eelLengths_, eelLengths_+sizeof(eelLengths_)/s > 77 int maxCuts = 2; > 78 int _ = 0; > 79 END > 80 CASE(2) > 81 int eelLengths_[] = {34, 10, 48}; > 82 vector <int> eelLengths(eelLengths_, eelLengths_+sizeof(eelLengths_)/s > 83 int maxCuts = 4; > 84 int _ = 5; > 85 END > 86 CASE(3) > 87 int eelLengths_[] = {30, 50, 30, 50}; > 88 vector <int> eelLengths(eelLengths_, eelLengths_+sizeof(eelLengths_)/s > 89 int maxCuts = 350; > 90 int _ = 16; > 91 END > 92 /* > 93 CASE(4) > 94 int eelLengths_[] = ; > 95 vector <int> eelLengths(eelLengths_, eelLengths_+sizeof(eelLengths_)/s > 96 int maxCuts = ; > 97 int _ = ; > 98 END > 99 CASE(5) > 100 int eelLengths_[] = ; > 101 vector <int> eelLengths(eelLengths_, eelLengths_+sizeof(eelLengths_)/s > 102 int maxCuts = ; > 103 int _ = ; > 104 END > 105 */ > 106 } > 107 // END CUT HERE
Added SRM/528/1B.cpp version [e3b7dabae0461c08]
> 1 #include <iostream> > 2 #include <sstream> > 3 #include <iomanip> > 4 #include <vector> > 5 #include <string> > 6 #include <map> > 7 #include <set> > 8 #include <algorithm> > 9 #include <numeric> > 10 #include <iterator> > 11 #include <functional> > 12 #include <complex> > 13 #include <queue> > 14 #include <stack> > 15 #include <cmath> > 16 #include <cassert> > 17 #include <cstring> > 18 #ifdef __GNUC__ > 19 #include <ext/hash_map> > 20 #define unordered_map __gnu_cxx::hash_map > 21 #else > 22 #include <unordered_map> > 23 #endif > 24 using namespace std; > 25 typedef long long LL; > 26 typedef complex<double> CMP; > 27 > 28 template<typename T> > 29 struct DP2x > 30 { > 31 const int N1, N2; > 32 vector<T> data; > 33 DP2x(int, int N2, const T& t = T()) > 34 : N1(2), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)<( > 35 T& operator()(int i1, int i2) > 36 { i1&=1; return data[ (i1*N2)+i2 ]; } > 37 void swap(DP2x& rhs) > 38 { data.swap(rhs.data); } > 39 }; > 40 > 41 class SPartition { public: > 42 long long getCount(string s) > 43 { > 44 if( s.size()%2 != 0 ) > 45 return 0; > 46 > 47 int N = s.size()/2; > 48 DP2x<LL> dp(s.size()+1, 1<<N); > 49 for(int i=s.size(); i>=0; --i) > 50 for(int bits=0,ni=min(N,i); bits<(1<<ni); ++bits) > 51 { > 52 if( i == s.size() ) > 53 dp(i,bits) = (bits==0 ? 1 : 0); > 54 else { > 55 if( bits == 0 ) { > 56 dp(i, bits) = dp(i+1, 1) * 2; > 57 } else { > 58 int iMax = 0; > 59 while( (2<<iMax) <= bits ) > 60 ++iMax; > 61 int oldb = s[i-1-iMax]; > 62 int newb = s[i]; > 63 LL tot = 0; > 64 if( oldb == newb ) > 65 tot += dp(i+1, (bits &~ > 66 if( (bits<<1 | 1) < (1<<N) ) > 67 tot += dp(i+1, bits<<1 | > 68 dp(i,bits) = tot; > 69 } > 70 } > 71 } > 72 return dp(0, 0); > 73 } > 74 }; > 75 > 76 // BEGIN CUT HERE > 77 #include <ctime> > 78 double start_time; string timer() > 79 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 80 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 81 { os << "{ "; > 82 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 83 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 84 void verify_case(const long long& Expected, const long long& Received) { > 85 bool ok = (Expected == Received); > 86 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 87 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 88 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 89 #define END verify_case(_, SPartition().getCount(s));} > 90 int main(){ > 91 > 92 CASE(0) > 93 string s = "oxox"; > 94 long long _ = 2LL; > 95 END > 96 CASE(1) > 97 string s = "oooxxx"; > 98 long long _ = 0LL; > 99 END > 100 CASE(2) > 101 string s = "xoxxox"; > 102 long long _ = 4LL; > 103 END > 104 CASE(3) > 105 string s = "xo"; > 106 long long _ = 0LL; > 107 END > 108 CASE(4) > 109 string s = "ooooxoox"; > 110 long long _ = 8LL; > 111 END > 112 CASE(5) > 113 string s = "ooxxoxox"; > 114 long long _ = 8LL; > 115 END > 116 CASE(6) > 117 string s = "oxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxox"; > 118 long long _ = -1LL; > 119 END > 120 /* > 121 CASE(7) > 122 string s = ; > 123 long long _ = LL; > 124 END > 125 */ > 126 } > 127 // END CUT HERE
Added SRM/528/1C.cpp version [db458a8bf7c0ef4d]
> 1 #include <iostream> > 2 #include <sstream> > 3 #include <iomanip> > 4 #include <vector> > 5 #include <string> > 6 #include <map> > 7 #include <set> > 8 #include <algorithm> > 9 #include <numeric> > 10 #include <iterator> > 11 #include <functional> > 12 #include <complex> > 13 #include <queue> > 14 #include <stack> > 15 #include <cmath> > 16 #include <cassert> > 17 #include <cstring> > 18 #ifdef __GNUC__ > 19 #include <ext/hash_map> > 20 #define unordered_map __gnu_cxx::hash_map > 21 #else > 22 #include <unordered_map> > 23 #endif > 24 using namespace std; > 25 typedef long long LL; > 26 typedef complex<double> CMP; > 27 > 28 template<typename T> > 29 struct DP2x > 30 { > 31 const int N1, N2; > 32 vector<T> data; > 33 DP2x(int, int N2, const T& t = T()) > 34 : N1(2), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)<( > 35 T& operator()(int i1, int i2) > 36 { i1&=1; return data[ (i1*N2)+i2 ]; } > 37 void swap(DP2x& rhs) > 38 { data.swap(rhs.data); } > 39 }; > 40 > 41 class ColorfulCookie { public: > 42 int getMaximum(vector <int> cookies, int P1, int P2) > 43 { > 44 int L = 0; > 45 int R = accumulate(cookies.begin(), cookies.end(), 0) / (P1+P2) > 46 while( R-L > 1 ) { // [L, R) > 47 int C = (L+R) / 2; > 48 (possible(cookies, P1, P2, C) ? L : R) = C; > 49 } > 50 return L * (P1+P2); > 51 } > 52 > 53 bool possible(const vector<int>& C, int P1, int P2, int Times) > 54 { > 55 DP2x<int> maxP2forP1(C.size()+1, Times+1, -1); > 56 maxP2forP1(0,0) = 0; > 57 for(int i=0; i<C.size(); ++i) > 58 for(int n=0; n<=Times; ++n) { > 59 maxP2forP1(i+1,n) = maxP2forP1(i,n); > 60 for(int a=0; a<=n; ++a) { > 61 if( n-a>=0 && maxP2forP1(i,n-a)>=0 && C[ > 62 maxP2forP1(i+1,n) = max(maxP2for > 63 maxP2forP1(i,n-a) + min( > 64 ); > 65 } > 66 } > 67 return maxP2forP1(C.size(), Times) >= Times; > 68 } > 69 }; > 70 > 71 // BEGIN CUT HERE > 72 #include <ctime> > 73 double start_time; string timer() > 74 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 75 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 76 { os << "{ "; > 77 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 78 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 79 void verify_case(const int& Expected, const int& Received) { > 80 bool ok = (Expected == Received); > 81 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 82 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 83 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 84 #define END verify_case(_, ColorfulCookie().getMaximum(cookies, P1, P2));} > 85 int main(){ > 86 > 87 CASE(0) > 88 int cookies_[] = {100, 100}; > 89 vector <int> cookies(cookies_, cookies_+sizeof(cookies_)/sizeof(*cooki > 90 int P1 = 50; > 91 int P2 = 50; > 92 int _ = 200; > 93 END > 94 CASE(1) > 95 int cookies_[] = {50, 250, 50}; > 96 vector <int> cookies(cookies_, cookies_+sizeof(cookies_)/sizeof(*cooki > 97 int P1 = 50; > 98 int P2 = 100; > 99 int _ = 300; > 100 END > 101 CASE(2) > 102 int cookies_[] = {2000}; > 103 vector <int> cookies(cookies_, cookies_+sizeof(cookies_)/sizeof(*cooki > 104 int P1 = 100; > 105 int P2 = 200; > 106 int _ = 0; > 107 END > 108 CASE(3) > 109 int cookies_[] = {123, 456, 789, 555}; > 110 vector <int> cookies(cookies_, cookies_+sizeof(cookies_)/sizeof(*cooki > 111 int P1 = 58; > 112 int P2 = 158; > 113 int _ = 1728; > 114 END > 115 /* > 116 CASE(4) > 117 int cookies_[] = ; > 118 vector <int> cookies(cookies_, cookies_+sizeof(cookies_)/sizeof(*cooki > 119 int P1 = ; > 120 int P2 = ; > 121 int _ = ; > 122 END > 123 CASE(5) > 124 int cookies_[] = ; > 125 vector <int> cookies(cookies_, cookies_+sizeof(cookies_)/sizeof(*cooki > 126 int P1 = ; > 127 int P2 = ; > 128 int _ = ; > 129 END > 130 */ > 131 } > 132 // END CUT HERE
Modified lib/typical/dp.cpp from [ae16b2462960bb78] to [feb5fdb1e50b8e31].
8 : N1(N1), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)< 8 : N1(N1), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)< 9 T& operator()(int i1, int i2) 9 T& operator()(int i1, int i2) 10 { return data[ (i1*N2)+i2 ]; } 10 { return data[ (i1*N2)+i2 ]; } 11 void swap(DP2& rhs) 11 void swap(DP2& rhs) 12 { data.swap(rhs.data); } 12 { data.swap(rhs.data); } 13 }; 13 }; 14 14 15 // Tested: Codeforces #13 C | 15 // Tested: Codeforces #13 C, SRM 528 Lv2 16 template<typename T> 16 template<typename T> 17 struct DP2x 17 struct DP2x 18 { 18 { 19 const int N1, N2; 19 const int N1, N2; 20 vector<T> data; 20 vector<T> data; 21 DP2x(int, int N2, const T& t = T()) 21 DP2x(int, int N2, const T& t = T()) 22 : N1(2), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)<( 22 : N1(2), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)<(