Overview
| SHA1 Hash: | fc5b59158c61311b60208833817e6e761dc9df66 |
|---|---|
| Date: | 2014-03-04 11:01:53 |
| User: | kinaba |
| Comment: | 610 |
| 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/610-U/1A.cpp version [de7a6642f3923063]
> 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 <tuple> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class TheMatrix { public: > 23 int MaxArea(vector <string> board) > 24 { > 25 const int H = board.size(), W = board[0].size(); > 26 vector<vector<int>> yL(H, vector<int>(W)); > 27 > 28 for(int y=0; y<H; ++y) > 29 for(int x=0; x<W; ++x) > 30 for(yL[y][x]=1; y+yL[y][x]<H; ++yL[y][x]) > 31 if(board[y+yL[y][x]][x] == board[y+yL[y][x]-1][x > 32 break; > 33 > 34 int best = 0; > 35 for(int y=0; y<H; ++y) > 36 for(int x=0; x<W; ++x) > 37 { > 38 int h = yL[y][x]; > 39 best = max(best, h*1); > 40 for(int xd=1; x+xd<W; ++xd) if(board[y][x+xd] == board[y > 41 h = min(h, yL[y][x+xd]); > 42 best = max(best, h*(xd+1)); > 43 } > 44 } > 45 return best; > 46 } > 47 }; > 48 > 49 // BEGIN CUT HERE > 50 #include <ctime> > 51 double start_time; string timer() > 52 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 53 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 54 { os << "{ "; > 55 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 56 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 57 void verify_case(const int& Expected, const int& Received) { > 58 bool ok = (Expected == Received); > 59 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 60 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 61 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 62 #define END verify_case(_, TheMatrix().MaxArea(board));} > 63 int main(){ > 64 CASE(0) > 65 string board_[] = {"1", > 66 "0"}; > 67 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 68 int _ = 2; > 69 END > 70 CASE(1) > 71 string board_[] = {"0000"}; > 72 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 73 int _ = 1; > 74 END > 75 CASE(2) > 76 string board_[] = {"01"}; > 77 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 78 int _ = 2; > 79 END > 80 CASE(3) > 81 string board_[] = {"001", > 82 "000", > 83 "100"}; > 84 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 85 int _ = 2; > 86 END > 87 CASE(4) > 88 string board_[] = {"0"}; > 89 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 90 int _ = 1; > 91 END > 92 CASE(5) > 93 string board_[] = {"101", > 94 "010"}; > 95 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 96 int _ = 6; > 97 END > 98 CASE(6) > 99 string board_[] = {"101", > 100 "011", > 101 "101", > 102 "010"}; > 103 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 104 int _ = 8; > 105 END > 106 CASE(7) > 107 string board_[] = {"11001110011000110001111001001110110011010110001011", > 108 "10100100010111111011111001011110101111010011100001", > 109 "11101111001110100110010101101100011100101000010001", > 110 "01000010001010101100010011111000100100110111111000", > 111 "10110100000101100000111000100001011101111101010010", > 112 "00111010000011100001110110010011010110010011100100", > 113 "01100001111101001101001101100001111000111001101010", > 114 "11010000000011011010100010000000111011001001100101", > 115 "10100000000100010100100011010100110110110001000001", > 116 "01101010101100001100000110100110100000010100100010", > 117 "11010000001110111111011010011110001101100011100010", > 118 "11101111000000011010011100100001100011111111110111", > 119 "11000001101100100011000110111010011001010100000001", > 120 "00100001111001010000101101100010000001100100001000", > 121 "01001110110111101011010000111111101011000110010111", > 122 "01001010000111111001100000100010101100100101010100", > 123 "11111101001101110011011011011000111001101100011011", > 124 "10000100110111000001110110010000000000111100101101", > 125 "01010011101101101110000011000110011111001111011100", > 126 "01101010011111010000011001111101011010011100001101", > 127 "11011000011000110010101111100000101011011111101100", > 128 "11100001001000110010100011001010101101001010001100", > 129 "11011011001100111101001100111100000101011101101011", > 130 "11110111100100101011100101111101000111001111110111", > 131 "00011001100110111100111100001100101001111100001111", > 132 "10001111100101110111001111100000000011110000100111", > 133 "10101010110110100110010001001010000111100110100011", > 134 "01100110100000001110101001101011001010001101110101", > 135 "10110101110100110110101001100111110000101111100110", > 136 "01011000001001101110100001101001110011001001110001", > 137 "00100101010001100110110101001010010100001011000011", > 138 "00011101100100001010100000000011000010100110011100", > 139 "11001001011000000101111111000000110010001101101110", > 140 "10101010110110010000010011001100110101110100111011", > 141 "01101001010111010001101000100011101001110101000110", > 142 "00110101101110110001110101110010100100110000101101", > 143 "11010101000111010011110011000001101111010011110011", > 144 "10010000010001110011011101001110110010001100011100", > 145 "00111101110001001100101001110100110010100110110000", > 146 "00010011011000101000100001101110111100100000010100", > 147 "01101110001101000001001000001011101010011101011110", > 148 "00000100110011001011101011110011011101100001110111", > 149 "00110011110000011001011100001110101010100110010110", > 150 "00111001010011011111010100000100100000101101110001", > 151 "10101101101110111110000011111011001011100011110001", > 152 "00101110010101111000001010110100001110111011100011", > 153 "01111110010100111010110001111000111101110100111011"}; > 154 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 155 int _ = 12; > 156 END > 157 /* > 158 CASE(8) > 159 string board_[] = ; > 160 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 161 int _ = ; > 162 END > 163 CASE(9) > 164 string board_[] = ; > 165 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 166 int _ = ; > 167 END > 168 */ > 169 } > 170 // END CUT HERE
Added SRM/610-U/1B.cpp version [4609d5c332ae9be3]
> 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 <tuple> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class AlbertoTheAviator { public: > 23 int MaximumFlights(int F, vector <int> duration, vector <int> refuel) > 24 { > 25 const int N = duration.size(); > 26 vector<pair<int,int>> mp; > 27 for(int i=0; i<N; ++i) > 28 mp.emplace_back(duration[i], refuel[i]); > 29 > 30 // Larger refuel first. > 31 sort(mp.begin(), mp.end(), [&](const pair<int,int>& lhs, const p > 32 if(lhs.second != rhs.second) > 33 return lhs.second > rhs.second; > 34 return lhs.first < rhs.first; > 35 }); > 36 > 37 const int BAD = -0x3fffffff; > 38 vector<int> dp(F+1, BAD); > 39 dp[F] = 0; > 40 for(auto& mpi: mp) { > 41 int minus = mpi.first; > 42 int plus = mpi.second; > 43 > 44 vector<int> dp2 = dp; > 45 for(int f=minus; f<=F; ++f) > 46 dp2[f-minus+plus] = max(dp2[f-minus+plus], dp[f] > 47 dp.swap(dp2); > 48 } > 49 > 50 return *max_element(dp.begin(), dp.end()); > 51 } > 52 }; > 53 > 54 // BEGIN CUT HERE > 55 #include <ctime> > 56 double start_time; string timer() > 57 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 58 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 59 { os << "{ "; > 60 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 61 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 62 void verify_case(const int& Expected, const int& Received) { > 63 bool ok = (Expected == Received); > 64 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 65 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 66 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 67 #define END verify_case(_, AlbertoTheAviator().MaximumFlights(F, duration, > 68 int main(){ > 69 > 70 CASE(0) > 71 int F = 10; > 72 int duration_[] = {10}; > 73 vector <int> duration(duration_, duration_+sizeof(duration_)/sizeof(*d > 74 int refuel_[] = {0}; > 75 vector <int> refuel(refuel_, refuel_+sizeof(refuel_)/sizeof(*refuel_)) > 76 int _ = 1; > 77 END > 78 CASE(1) > 79 int F = 10; > 80 int duration_[] = {8, 4}; > 81 vector <int> duration(duration_, duration_+sizeof(duration_)/sizeof(*d > 82 int refuel_[] = {0, 2}; > 83 vector <int> refuel(refuel_, refuel_+sizeof(refuel_)/sizeof(*refuel_)) > 84 int _ = 2; > 85 END > 86 CASE(2) > 87 int F = 12; > 88 int duration_[] = {4, 8, 2, 1}; > 89 vector <int> duration(duration_, duration_+sizeof(duration_)/sizeof(*d > 90 int refuel_[] = {2, 0, 0, 0}; > 91 vector <int> refuel(refuel_, refuel_+sizeof(refuel_)/sizeof(*refuel_)) > 92 int _ = 3; > 93 END > 94 CASE(3) > 95 int F = 9; > 96 int duration_[] = {4, 6}; > 97 vector <int> duration(duration_, duration_+sizeof(duration_)/sizeof(*d > 98 int refuel_[] = {0, 1}; > 99 vector <int> refuel(refuel_, refuel_+sizeof(refuel_)/sizeof(*refuel_)) > 100 int _ = 2; > 101 END > 102 CASE(4) > 103 int F = 100; > 104 int duration_[] = {101}; > 105 vector <int> duration(duration_, duration_+sizeof(duration_)/sizeof(*d > 106 int refuel_[] = {100}; > 107 vector <int> refuel(refuel_, refuel_+sizeof(refuel_)/sizeof(*refuel_)) > 108 int _ = 0; > 109 END > 110 CASE(5) > 111 int F = 1947; > 112 int duration_[] = {2407, 2979, 1269, 2401, 3227, 2230, 3991, 2133, 3338, > 113 vector <int> duration(duration_, duration_+sizeof(duration_)/sizeof(*d > 114 int refuel_[] = {2406, 793, 905, 2400, 1789, 2229, 1378, 2132, 1815, 355 > 115 vector <int> refuel(refuel_, refuel_+sizeof(refuel_)/sizeof(*refuel_)) > 116 int _ = 3; > 117 END > 118 CASE(6) > 119 int F = 5000; > 120 int duration_[] = {948,914,915,945,952,939,925,951,957,978,926,973,986,9 > 121 vector <int> duration(duration_, duration_+sizeof(duration_)/sizeof(*d > 122 int refuel_[] = {819,852,834,789,875,833,760,887,796,831,900,805,758,794 > 123 vector <int> refuel(refuel_, refuel_+sizeof(refuel_)/sizeof(*refuel_)) > 124 int _ = -1; > 125 END > 126 /* > 127 CASE(7) > 128 int F = ; > 129 int duration_[] = ; > 130 vector <int> duration(duration_, duration_+sizeof(duration_)/sizeof(*d > 131 int refuel_[] = ; > 132 vector <int> refuel(refuel_, refuel_+sizeof(refuel_)/sizeof(*refuel_)) > 133 int _ = ; > 134 END > 135 */ > 136 } > 137 // END CUT1 HERE900
Added SRM/610-U/1C-U.cpp version [341006a06a5e7b6d]
> 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 <tuple> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class MiningGoldHard { public: > 23 int GetMaximumGold(int N, int M, vector <int> event_i, vector <int> even > 24 { > 25 return solve(N, event_i, event_di) + solve(M, event_j, event_dj) > 26 } > 27 > 28 int solve(int W, const vector<int>& e, const vector<int>& d) > 29 { > 30 vector<int> dp(W+1, 0); > 31 for(int x=0; x<=W; ++x) > 32 dp[x] = W - abs(x-e[0]); > 33 > 34 for(int i=0; i<d.size(); ++i) { > 35 vector<int> dp2(W+1, 0); > 36 for(int x=0; x<=W; ++x) > 37 dp2[x] = W - abs(x-e[i+1]); > 38 > 39 deque<int> q; > 40 int px = 0; > 41 for(px=0; px<=d[i] && px<=W; ++px) { > 42 while(!q.empty() && dp[q.back()] < dp[px]) > 43 q.pop_back(); > 44 q.push_back(px); > 45 } > 46 > 47 for(int x=0; x<=W; ++x) { > 48 while(q.front() < x-d[i]) > 49 q.pop_front(); > 50 > 51 dp2[x] += dp[q.front()]; > 52 > 53 if(px<=W) { > 54 while(!q.empty() && dp[q.back()] < dp[px > 55 q.pop_back(); > 56 q.push_back(px); > 57 > 58 ++px; > 59 } > 60 } > 61 > 62 dp.swap(dp2); > 63 } > 64 return *max_element(dp.begin(), dp.end()); > 65 } > 66 }; > 67 > 68 // BEGIN CUT HERE > 69 #include <ctime> > 70 double start_time; string timer() > 71 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 72 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 73 { os << "{ "; > 74 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 75 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 76 void verify_case(const int& Expected, const int& Received) { > 77 bool ok = (Expected == Received); > 78 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 79 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 80 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 81 #define END verify_case(_, MiningGoldHard().GetMaximumGold(N, M, event_i, e > 82 int main(){ > 83 > 84 CASE(0) > 85 int N = 3; > 86 int M = 3; > 87 int event_i_[] = {1}; > 88 vector <int> event_i(event_i_, event_i_+sizeof(event_i_)/sizeof(*event > 89 int event_j_[] = {1}; > 90 vector <int> event_j(event_j_, event_j_+sizeof(event_j_)/sizeof(*event > 91 vector <int> event_di; > 92 vector <int> event_dj; > 93 int _ = 6; > 94 END > 95 CASE(1) > 96 int N = 3; > 97 int M = 3; > 98 int event_i_[] = {0, 2}; > 99 vector <int> event_i(event_i_, event_i_+sizeof(event_i_)/sizeof(*event > 100 int event_j_[] = {0, 2}; > 101 vector <int> event_j(event_j_, event_j_+sizeof(event_j_)/sizeof(*event > 102 int event_di_[] = {1}; > 103 vector <int> event_di(event_di_, event_di_+sizeof(event_di_)/sizeof(*e > 104 int event_dj_[] = {1}; > 105 vector <int> event_dj(event_dj_, event_dj_+sizeof(event_dj_)/sizeof(*e > 106 int _ = 10; > 107 END > 108 CASE(2) > 109 int N = 4; > 110 int M = 2; > 111 int event_i_[] = {1, 4, 4}; > 112 vector <int> event_i(event_i_, event_i_+sizeof(event_i_)/sizeof(*event > 113 int event_j_[] = {1, 2, 0}; > 114 vector <int> event_j(event_j_, event_j_+sizeof(event_j_)/sizeof(*event > 115 int event_di_[] = {1, 1}; > 116 vector <int> event_di(event_di_, event_di_+sizeof(event_di_)/sizeof(*e > 117 int event_dj_[] = {1, 1}; > 118 vector <int> event_dj(event_dj_, event_dj_+sizeof(event_dj_)/sizeof(*e > 119 int _ = 15; > 120 END > 121 CASE(3) > 122 int N = 6; > 123 int M = 6; > 124 int event_i_[] = {0, 2, 1, 5, 6, 4}; > 125 vector <int> event_i(event_i_, event_i_+sizeof(event_i_)/sizeof(*event > 126 int event_j_[] = {4, 3, 1, 6, 2, 0}; > 127 vector <int> event_j(event_j_, event_j_+sizeof(event_j_)/sizeof(*event > 128 int event_di_[] = {2, 3, 1, 5, 6}; > 129 vector <int> event_di(event_di_, event_di_+sizeof(event_di_)/sizeof(*e > 130 int event_dj_[] = {2, 4, 0, 5, 1}; > 131 vector <int> event_dj(event_dj_, event_dj_+sizeof(event_dj_)/sizeof(*e > 132 int _ = 63; > 133 END > 134 CASE(4) > 135 int N = 72; > 136 int M = 90; > 137 int event_i_[] = {9, 9, 42, 64, 37, 4, 67, 65, 20, 18, 25, 45, 19, 57, 3 > 138 vector <int> event_i(event_i_, event_i_+sizeof(event_i_)/sizeof(*event > 139 int event_j_[] = {37, 47, 48, 69, 56, 22, 40, 52, 43, 46, 64, 24, 48, 54 > 140 vector <int> event_j(event_j_, event_j_+sizeof(event_j_)/sizeof(*event > 141 int event_di_[] = {56, 5, 21, 5, 22, 5, 45, 4, 44, 20, 68, 63, 37, 14, 4 > 142 vector <int> event_di(event_di_, event_di_+sizeof(event_di_)/sizeof(*e > 143 int event_dj_[] = {77, 73, 42, 80, 43, 24, 81, 68, 40, 86, 1, 76, 43, 10 > 144 vector <int> event_dj(event_dj_, event_dj_+sizeof(event_dj_)/sizeof(*e > 145 int _ = 5810; > 146 END > 147 CASE(5) > 148 int N = 1000000; > 149 int M = 1000000; > 150 int event_i_[] = {9, 9, 42, 64, 37, 4, 67, 65, 20, 18, 25, 45, 19, 57, 3 > 151 vector <int> event_i(event_i_, event_i_+sizeof(event_i_)/sizeof(*event > 152 int event_j_[] = {37, 47, 48, 69, 56, 22, 40, 52, 43, 46, 64, 24, 48, 54 > 153 vector <int> event_j(event_j_, event_j_+sizeof(event_j_)/sizeof(*event > 154 int event_di_[] = {56, 5, 21, 5, 22, 5, 45, 4, 44, 20, 68, 63, 37, 14, 4 > 155 vector <int> event_di(event_di_, event_di_+sizeof(event_di_)/sizeof(*e > 156 int event_dj_[] = {77, 73, 42, 80, 43, 24, 81, 68, 40, 86, 1, 76, 43, 10 > 157 vector <int> event_dj(event_dj_, event_dj_+sizeof(event_dj_)/sizeof(*e > 158 int _ = -1; > 159 END > 160 /* > 161 CASE(6) > 162 int N = 1000000; > 163 int M = 1000000; > 164 int event_i_[] = ; > 165 vector <int> event_i(event_i_, event_i_+sizeof(event_i_)/sizeof(*event > 166 int event_j_[] = ; > 167 vector <int> event_j(event_j_, event_j_+sizeof(event_j_)/sizeof(*event > 168 int event_di_[] = ; > 169 vector <int> event_di(event_di_, event_di_+sizeof(event_di_)/sizeof(*e > 170 int event_dj_[] = ; > 171 vector <int> event_dj(event_dj_, event_dj_+sizeof(event_dj_)/sizeof(*e > 172 int _ = ; > 173 END > 174 */ > 175 } > 176 // END CUT HERE