Artifact Content
Not logged in

Artifact 4609d5c332ae9be308826276329095790c5e1c6b


#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <tuple>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;

class AlbertoTheAviator { public:
	int MaximumFlights(int F, vector <int> duration, vector <int> refuel)
	{
		const int N = duration.size();
		vector<pair<int,int>> mp;
		for(int i=0; i<N; ++i)
			mp.emplace_back(duration[i], refuel[i]);

		// Larger refuel first.
		sort(mp.begin(), mp.end(), [&](const pair<int,int>& lhs, const pair<int,int>& rhs){
			if(lhs.second != rhs.second)
				return lhs.second > rhs.second;
			return lhs.first < rhs.first;
		});

		const int BAD = -0x3fffffff;
		vector<int> dp(F+1, BAD);
		dp[F] = 0;
		for(auto& mpi: mp) {
			int minus = mpi.first;
			int plus = mpi.second;

			vector<int> dp2 = dp;
			for(int f=minus; f<=F; ++f)
				dp2[f-minus+plus] = max(dp2[f-minus+plus], dp[f]+1);
			dp.swap(dp2);
		}

		return *max_element(dp.begin(), dp.end());
	}
};

// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
 { os << "{ ";
   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
 bool ok = (Expected == Received);
 if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END	 verify_case(_, AlbertoTheAviator().MaximumFlights(F, duration, refuel));}
int main(){

CASE(0)
	int F = 10; 
	int duration_[] = {10};
	  vector <int> duration(duration_, duration_+sizeof(duration_)/sizeof(*duration_)); 
	int refuel_[] = {0};
	  vector <int> refuel(refuel_, refuel_+sizeof(refuel_)/sizeof(*refuel_)); 
	int _ = 1; 
END
CASE(1)
	int F = 10; 
	int duration_[] = {8, 4};
	  vector <int> duration(duration_, duration_+sizeof(duration_)/sizeof(*duration_)); 
	int refuel_[] = {0, 2};
	  vector <int> refuel(refuel_, refuel_+sizeof(refuel_)/sizeof(*refuel_)); 
	int _ = 2; 
END
CASE(2)
	int F = 12; 
	int duration_[] = {4, 8, 2, 1};
	  vector <int> duration(duration_, duration_+sizeof(duration_)/sizeof(*duration_)); 
	int refuel_[] = {2, 0, 0, 0};
	  vector <int> refuel(refuel_, refuel_+sizeof(refuel_)/sizeof(*refuel_)); 
	int _ = 3; 
END
CASE(3)
	int F = 9; 
	int duration_[] = {4, 6};
	  vector <int> duration(duration_, duration_+sizeof(duration_)/sizeof(*duration_)); 
	int refuel_[] = {0, 1};
	  vector <int> refuel(refuel_, refuel_+sizeof(refuel_)/sizeof(*refuel_)); 
	int _ = 2; 
END
CASE(4)
	int F = 100; 
	int duration_[] = {101};
	  vector <int> duration(duration_, duration_+sizeof(duration_)/sizeof(*duration_)); 
	int refuel_[] = {100};
	  vector <int> refuel(refuel_, refuel_+sizeof(refuel_)/sizeof(*refuel_)); 
	int _ = 0; 
END
CASE(5)
	int F = 1947; 
	int duration_[] = {2407, 2979, 1269, 2401, 3227, 2230, 3991, 2133, 3338, 356, 2535, 3859, 3267, 365};
	  vector <int> duration(duration_, duration_+sizeof(duration_)/sizeof(*duration_)); 
	int refuel_[] = {2406, 793, 905, 2400, 1789, 2229, 1378, 2132, 1815, 355, 72, 3858, 3266, 364};
	  vector <int> refuel(refuel_, refuel_+sizeof(refuel_)/sizeof(*refuel_)); 
	int _ = 3; 
END
CASE(6)
	int F = 5000; 
	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};
	  vector <int> duration(duration_, duration_+sizeof(duration_)/sizeof(*duration_)); 
	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};
	  vector <int> refuel(refuel_, refuel_+sizeof(refuel_)/sizeof(*refuel_)); 
	int _ = -1; 
END
/*
CASE(7)
	int F = ; 
	int duration_[] = ;
	  vector <int> duration(duration_, duration_+sizeof(duration_)/sizeof(*duration_)); 
	int refuel_[] = ;
	  vector <int> refuel(refuel_, refuel_+sizeof(refuel_)/sizeof(*refuel_)); 
	int _ = ; 
END
*/
}
// END CUT1 HERE900