Artifact Content
Not logged in

Artifact 3cbbfe4224f260a70a1d4ff093e669aaba5a1690


#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 KiwiJuice { public:
	int theProfit(int C, vector <int> bottles, vector <int> prices) 
	{
		best.clear();
		best.resize(1<<bottles.size(), -1);
		return rec((1<<bottles.size())-1, C, bottles, prices);
	}

	vector<int> best;
	int rec(int mask, int C, vector<int>& B, const vector<int>& P)
	{
		if( mask == 0 )
			return 0;
		if( best[mask] != -1 )
			return best[mask];
		int maxSc = 0;
		for(int subset=mask; subset; subset=((subset-1)&mask)) {
			int sum = 0;
			int bin = 0;
			for(int i=0; i<B.size(); ++i)
				if( subset & (1<<i) ) {
					sum += B[i];
					bin += 1;
				}
			int sc = P[C] * (sum/C);
			if(sum%C) sc += P[sum%C];
			sc += P[0] *  (bin-((sum/C)+(sum%C?1:0)));
			sc += rec(mask&~subset, C, B, P);
			maxSc = max(maxSc, sc);
		}
		return best[mask] = maxSc;
	}
};

// 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(_, KiwiJuice().theProfit(C, bottles, prices));}
int main(){

CASE(0)
	int C = 10; 
	int bottles_[] = {5, 8};
	  vector <int> bottles(bottles_, bottles_+sizeof(bottles_)/sizeof(*bottles_)); 
	int prices_[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10};
	  vector <int> prices(prices_, prices_+sizeof(prices_)/sizeof(*prices_)); 
	int _ = 10; 
END
CASE(1)
	int C = 10; 
	int bottles_[] = {5, 8};
	  vector <int> bottles(bottles_, bottles_+sizeof(bottles_)/sizeof(*bottles_)); 
	int prices_[] = {0, 0, 0, 0, 0, 10, 10, 10, 10, 10, 10};
	  vector <int> prices(prices_, prices_+sizeof(prices_)/sizeof(*prices_)); 
	int _ = 20; 
END
CASE(2)
	int C = 10; 
	int bottles_[] = {4, 5, 3, 7};
	  vector <int> bottles(bottles_, bottles_+sizeof(bottles_)/sizeof(*bottles_)); 
	int prices_[] = {14, 76, 12, 35, 6, 94, 26, 3, 93, 90, 420};
	  vector <int> prices(prices_, prices_+sizeof(prices_)/sizeof(*prices_)); 
	int _ = 625; 
END
CASE(3)
	int C = 1; 
	int bottles_[] = {0};
	  vector <int> bottles(bottles_, bottles_+sizeof(bottles_)/sizeof(*bottles_)); 
	int prices_[] = {1000000, 1000000};
	  vector <int> prices(prices_, prices_+sizeof(prices_)/sizeof(*prices_)); 
	int _ = 1000000; 
END
CASE(4)
	int C = 49; 
	int bottles_[] = {2, 47, 24, 14, 0, 32, 9, 12, 31, 46, 39, 12, 16, 22, 29};
	  vector <int> bottles(bottles_, bottles_+sizeof(bottles_)/sizeof(*bottles_)); 
	int prices_[] = {428668, 995687, 128567, 37241, 496916, 238624, 304781, 997819, 85856, 417008,
398570, 951499, 750349, 333625, 927594, 188616, 942498, 259414, 654344, 354809,
25303, 226854, 98578, 207140, 305527, 358343, 393213, 256248, 282644, 103327,
667191, 103402, 609183, 619323, 189127, 518006, 778846, 400460, 128334, 795097,
605203, 669142, 121825, 934404, 837430, 554265, 610818, 546228, 80784, 949440};
	  vector <int> prices(prices_, prices_+sizeof(prices_)/sizeof(*prices_)); 
	int _ = 12873962; 
END
CASE(5)
	int C = 10; 
	int bottles_[] = {2,3,5};
	  vector <int> bottles(bottles_, bottles_+sizeof(bottles_)/sizeof(*bottles_)); 
	  int prices_[] = {0,0,9,9,0,9,0,0,0,0,99};
	  vector <int> prices(prices_, prices_+sizeof(prices_)/sizeof(*prices_)); 
	int _ = 99; 
END
/*
CASE(6)
	int C = ; 
	int bottles_[] = ;
	  vector <int> bottles(bottles_, bottles_+sizeof(bottles_)/sizeof(*bottles_)); 
	int prices_[] = ;
	  vector <int> prices(prices_, prices_+sizeof(prices_)/sizeof(*prices_)); 
	int _ = ; 
END
*/
}
// END CUT HERE