fc5b59158c 2014-03-04 kinaba: #include <iostream> fc5b59158c 2014-03-04 kinaba: #include <sstream> fc5b59158c 2014-03-04 kinaba: #include <iomanip> fc5b59158c 2014-03-04 kinaba: #include <vector> fc5b59158c 2014-03-04 kinaba: #include <string> fc5b59158c 2014-03-04 kinaba: #include <map> fc5b59158c 2014-03-04 kinaba: #include <set> fc5b59158c 2014-03-04 kinaba: #include <algorithm> fc5b59158c 2014-03-04 kinaba: #include <numeric> fc5b59158c 2014-03-04 kinaba: #include <iterator> fc5b59158c 2014-03-04 kinaba: #include <functional> fc5b59158c 2014-03-04 kinaba: #include <complex> fc5b59158c 2014-03-04 kinaba: #include <queue> fc5b59158c 2014-03-04 kinaba: #include <stack> fc5b59158c 2014-03-04 kinaba: #include <cmath> fc5b59158c 2014-03-04 kinaba: #include <cassert> fc5b59158c 2014-03-04 kinaba: #include <tuple> fc5b59158c 2014-03-04 kinaba: using namespace std; fc5b59158c 2014-03-04 kinaba: typedef long long LL; fc5b59158c 2014-03-04 kinaba: typedef complex<double> CMP; fc5b59158c 2014-03-04 kinaba: fc5b59158c 2014-03-04 kinaba: class AlbertoTheAviator { public: fc5b59158c 2014-03-04 kinaba: int MaximumFlights(int F, vector <int> duration, vector <int> refuel) fc5b59158c 2014-03-04 kinaba: { fc5b59158c 2014-03-04 kinaba: const int N = duration.size(); fc5b59158c 2014-03-04 kinaba: vector<pair<int,int>> mp; fc5b59158c 2014-03-04 kinaba: for(int i=0; i<N; ++i) fc5b59158c 2014-03-04 kinaba: mp.emplace_back(duration[i], refuel[i]); fc5b59158c 2014-03-04 kinaba: fc5b59158c 2014-03-04 kinaba: // Larger refuel first. fc5b59158c 2014-03-04 kinaba: sort(mp.begin(), mp.end(), [&](const pair<int,int>& lhs, const pair<int,int>& rhs){ fc5b59158c 2014-03-04 kinaba: if(lhs.second != rhs.second) fc5b59158c 2014-03-04 kinaba: return lhs.second > rhs.second; fc5b59158c 2014-03-04 kinaba: return lhs.first < rhs.first; fc5b59158c 2014-03-04 kinaba: }); fc5b59158c 2014-03-04 kinaba: fc5b59158c 2014-03-04 kinaba: const int BAD = -0x3fffffff; fc5b59158c 2014-03-04 kinaba: vector<int> dp(F+1, BAD); fc5b59158c 2014-03-04 kinaba: dp[F] = 0; fc5b59158c 2014-03-04 kinaba: for(auto& mpi: mp) { fc5b59158c 2014-03-04 kinaba: int minus = mpi.first; fc5b59158c 2014-03-04 kinaba: int plus = mpi.second; fc5b59158c 2014-03-04 kinaba: fc5b59158c 2014-03-04 kinaba: vector<int> dp2 = dp; fc5b59158c 2014-03-04 kinaba: for(int f=minus; f<=F; ++f) fc5b59158c 2014-03-04 kinaba: dp2[f-minus+plus] = max(dp2[f-minus+plus], dp[f]+1); fc5b59158c 2014-03-04 kinaba: dp.swap(dp2); fc5b59158c 2014-03-04 kinaba: } fc5b59158c 2014-03-04 kinaba: fc5b59158c 2014-03-04 kinaba: return *max_element(dp.begin(), dp.end()); fc5b59158c 2014-03-04 kinaba: } fc5b59158c 2014-03-04 kinaba: }; fc5b59158c 2014-03-04 kinaba: fc5b59158c 2014-03-04 kinaba: // BEGIN CUT HERE fc5b59158c 2014-03-04 kinaba: #include <ctime> fc5b59158c 2014-03-04 kinaba: double start_time; string timer() fc5b59158c 2014-03-04 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } fc5b59158c 2014-03-04 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) fc5b59158c 2014-03-04 kinaba: { os << "{ "; fc5b59158c 2014-03-04 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) fc5b59158c 2014-03-04 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } fc5b59158c 2014-03-04 kinaba: void verify_case(const int& Expected, const int& Received) { fc5b59158c 2014-03-04 kinaba: bool ok = (Expected == Received); fc5b59158c 2014-03-04 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; fc5b59158c 2014-03-04 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } fc5b59158c 2014-03-04 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); fc5b59158c 2014-03-04 kinaba: #define END verify_case(_, AlbertoTheAviator().MaximumFlights(F, duration, refuel));} fc5b59158c 2014-03-04 kinaba: int main(){ fc5b59158c 2014-03-04 kinaba: fc5b59158c 2014-03-04 kinaba: CASE(0) fc5b59158c 2014-03-04 kinaba: int F = 10; fc5b59158c 2014-03-04 kinaba: int duration_[] = {10}; fc5b59158c 2014-03-04 kinaba: vector <int> duration(duration_, duration_+sizeof(duration_)/sizeof(*duration_)); fc5b59158c 2014-03-04 kinaba: int refuel_[] = {0}; fc5b59158c 2014-03-04 kinaba: vector <int> refuel(refuel_, refuel_+sizeof(refuel_)/sizeof(*refuel_)); fc5b59158c 2014-03-04 kinaba: int _ = 1; fc5b59158c 2014-03-04 kinaba: END fc5b59158c 2014-03-04 kinaba: CASE(1) fc5b59158c 2014-03-04 kinaba: int F = 10; fc5b59158c 2014-03-04 kinaba: int duration_[] = {8, 4}; fc5b59158c 2014-03-04 kinaba: vector <int> duration(duration_, duration_+sizeof(duration_)/sizeof(*duration_)); fc5b59158c 2014-03-04 kinaba: int refuel_[] = {0, 2}; fc5b59158c 2014-03-04 kinaba: vector <int> refuel(refuel_, refuel_+sizeof(refuel_)/sizeof(*refuel_)); fc5b59158c 2014-03-04 kinaba: int _ = 2; fc5b59158c 2014-03-04 kinaba: END fc5b59158c 2014-03-04 kinaba: CASE(2) fc5b59158c 2014-03-04 kinaba: int F = 12; fc5b59158c 2014-03-04 kinaba: int duration_[] = {4, 8, 2, 1}; fc5b59158c 2014-03-04 kinaba: vector <int> duration(duration_, duration_+sizeof(duration_)/sizeof(*duration_)); fc5b59158c 2014-03-04 kinaba: int refuel_[] = {2, 0, 0, 0}; fc5b59158c 2014-03-04 kinaba: vector <int> refuel(refuel_, refuel_+sizeof(refuel_)/sizeof(*refuel_)); fc5b59158c 2014-03-04 kinaba: int _ = 3; fc5b59158c 2014-03-04 kinaba: END fc5b59158c 2014-03-04 kinaba: CASE(3) fc5b59158c 2014-03-04 kinaba: int F = 9; fc5b59158c 2014-03-04 kinaba: int duration_[] = {4, 6}; fc5b59158c 2014-03-04 kinaba: vector <int> duration(duration_, duration_+sizeof(duration_)/sizeof(*duration_)); fc5b59158c 2014-03-04 kinaba: int refuel_[] = {0, 1}; fc5b59158c 2014-03-04 kinaba: vector <int> refuel(refuel_, refuel_+sizeof(refuel_)/sizeof(*refuel_)); fc5b59158c 2014-03-04 kinaba: int _ = 2; fc5b59158c 2014-03-04 kinaba: END fc5b59158c 2014-03-04 kinaba: CASE(4) fc5b59158c 2014-03-04 kinaba: int F = 100; fc5b59158c 2014-03-04 kinaba: int duration_[] = {101}; fc5b59158c 2014-03-04 kinaba: vector <int> duration(duration_, duration_+sizeof(duration_)/sizeof(*duration_)); fc5b59158c 2014-03-04 kinaba: int refuel_[] = {100}; fc5b59158c 2014-03-04 kinaba: vector <int> refuel(refuel_, refuel_+sizeof(refuel_)/sizeof(*refuel_)); fc5b59158c 2014-03-04 kinaba: int _ = 0; fc5b59158c 2014-03-04 kinaba: END fc5b59158c 2014-03-04 kinaba: CASE(5) fc5b59158c 2014-03-04 kinaba: int F = 1947; fc5b59158c 2014-03-04 kinaba: int duration_[] = {2407, 2979, 1269, 2401, 3227, 2230, 3991, 2133, 3338, 356, 2535, 3859, 3267, 365}; fc5b59158c 2014-03-04 kinaba: vector <int> duration(duration_, duration_+sizeof(duration_)/sizeof(*duration_)); fc5b59158c 2014-03-04 kinaba: int refuel_[] = {2406, 793, 905, 2400, 1789, 2229, 1378, 2132, 1815, 355, 72, 3858, 3266, 364}; fc5b59158c 2014-03-04 kinaba: vector <int> refuel(refuel_, refuel_+sizeof(refuel_)/sizeof(*refuel_)); fc5b59158c 2014-03-04 kinaba: int _ = 3; fc5b59158c 2014-03-04 kinaba: END fc5b59158c 2014-03-04 kinaba: CASE(6) fc5b59158c 2014-03-04 kinaba: int F = 5000; fc5b59158c 2014-03-04 kinaba: int duration_[] = {948,914,915,945,952,939,925,951,957,978,926,973,986,949,992,932,968,916,946,901,929,956,976,941,938,980,984,906,979,907,923,931,963,964,932,910,909,981,969,997,936,930,956,949,903,914,954,945,913,969}; fc5b59158c 2014-03-04 kinaba: vector <int> duration(duration_, duration_+sizeof(duration_)/sizeof(*duration_)); fc5b59158c 2014-03-04 kinaba: int refuel_[] = {819,852,834,789,875,833,760,887,796,831,900,805,758,794,882,855,709,803,793,704,760,802,714,881,890,881,839,754,844,896,806,713,809,738,763,749,768,818,732,706,830,702,741,769,816,742,791,803,761,865}; fc5b59158c 2014-03-04 kinaba: vector <int> refuel(refuel_, refuel_+sizeof(refuel_)/sizeof(*refuel_)); fc5b59158c 2014-03-04 kinaba: int _ = -1; fc5b59158c 2014-03-04 kinaba: END fc5b59158c 2014-03-04 kinaba: /* fc5b59158c 2014-03-04 kinaba: CASE(7) fc5b59158c 2014-03-04 kinaba: int F = ; fc5b59158c 2014-03-04 kinaba: int duration_[] = ; fc5b59158c 2014-03-04 kinaba: vector <int> duration(duration_, duration_+sizeof(duration_)/sizeof(*duration_)); fc5b59158c 2014-03-04 kinaba: int refuel_[] = ; fc5b59158c 2014-03-04 kinaba: vector <int> refuel(refuel_, refuel_+sizeof(refuel_)/sizeof(*refuel_)); fc5b59158c 2014-03-04 kinaba: int _ = ; fc5b59158c 2014-03-04 kinaba: END fc5b59158c 2014-03-04 kinaba: */ fc5b59158c 2014-03-04 kinaba: } fc5b59158c 2014-03-04 kinaba: // END CUT1 HERE900