Artifact Content
Not logged in

Artifact 426e0d13a9708eff64138006dd5d6214d4754f75


#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 <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;

class FibonacciKnapsack { public:
	long long maximalCost(vector <string> items, string C_) 
	{
		LL C;
		stringstream(C_) >> C;

		vector< pair<LL,LL> > wp;
		for(int i=0; i<items.size(); ++i) {
			LL W, P;
			stringstream(items[i]) >> W >> P;
			wp.push_back( make_pair(W,P) );
		}
		sort( wp.begin(), wp.end() );

		LL lW = 0, lP = 0;
		for(int i=0; i<wp.size(); ++i)
			lW += wp[i].first, lP += wp[i].second;

		best = 0;
		rec( lW, lP, wp, wp.size()-1, C, 0 );
		return best;
	}

	LL best;
	void rec( LL lW, LL lP, vector< pair<LL,LL> >& wp, int i, LL w, LL cP )
	{
		if( lW <= w )
			best = max(best, lP+cP);
		if( lP+cP <= best )
			return;

		for(int k=i; k>=0 && wp[k].first==wp[i].first; --k)
		{
			lW -= wp[k].first;
			lP -= wp[k].second;
			if( w >= 0 )
				rec(lW, lP, wp, k-1, w, cP);
			w  -= wp[k].first;
			cP += wp[k].second;
		}
	}
};

// 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 long long& Expected, const long long& 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(_, FibonacciKnapsack().maximalCost(items, C));}
int main(){

CASE(0)
	string items_[] = {"5 555", "8 195", "13 651"};
	  vector <string> items(items_, items_+sizeof(items_)/sizeof(*items_)); 
	string C = "15"; 
	long long _ = 750LL; 
END
CASE(1)
	string items_[] = {"5 555", "8 195", "13 751"};
	  vector <string> items(items_, items_+sizeof(items_)/sizeof(*items_)); 
	string C = "15"; 
	long long _ = 751LL; 
END
CASE(2)
	string items_[] = {"55 1562", "5 814", "55 1962", "8 996", "2 716", "34 1792"};
	  vector <string> items(items_, items_+sizeof(items_)/sizeof(*items_)); 
	string C = "94"; 
	long long _ = 4568LL; 
END
CASE(3)
	string items_[] = {"13 89"};
	  vector <string> items(items_, items_+sizeof(items_)/sizeof(*items_)); 
	string C = "1"; 
	long long _ = 0LL; 
END
CASE(4)
	string items_[] = {"27777890035288 9419696870097445", 
 "53316291173 6312623457097563", 
 "165580141 8848283653257131"};
	  vector <string> items(items_, items_+sizeof(items_)/sizeof(*items_)); 
	string C = "27777900000000"; 
	long long _ = 15160907110354694LL; 
END
CASE(5)
	string items_[] = {"89 90", "55 54", "55 54", "34 35", "34 35", "34 35", "34 35", "21 23", "21 23", "21 23", "21 23", "21 23", "21 23", "21 23", "21 23", "13 14", "13 14", "13 14", "13 14", "13 14", "13 14", "13 14", "13 14", "13 14", "13 14", "13 14", "13 14", "13 14", "13 14", "13 14", "13 14", "8 10", "8 10", "8 10", "8 10", "8 10", "8 10", "8 10", "8 10", "8 10", "8 10", "8 10", "8 10", "8 10", "8 10", "8 10", "8 10", "8 10", "8 10", "8 10"};
	  vector <string> items(items_, items_+sizeof(items_)/sizeof(*items_)); 
	string C = "200"; 
	long long _ = 241LL;
END


}
// END CUT HERE