4fd800b3a8 2011-02-23        kinaba: #include <iostream>
4fd800b3a8 2011-02-23        kinaba: #include <sstream>
4fd800b3a8 2011-02-23        kinaba: #include <iomanip>
4fd800b3a8 2011-02-23        kinaba: #include <vector>
4fd800b3a8 2011-02-23        kinaba: #include <string>
4fd800b3a8 2011-02-23        kinaba: #include <map>
4fd800b3a8 2011-02-23        kinaba: #include <set>
4fd800b3a8 2011-02-23        kinaba: #include <algorithm>
4fd800b3a8 2011-02-23        kinaba: #include <numeric>
4fd800b3a8 2011-02-23        kinaba: #include <iterator>
4fd800b3a8 2011-02-23        kinaba: #include <functional>
4fd800b3a8 2011-02-23        kinaba: #include <complex>
4fd800b3a8 2011-02-23        kinaba: #include <queue>
4fd800b3a8 2011-02-23        kinaba: #include <stack>
4fd800b3a8 2011-02-23        kinaba: #include <cmath>
4fd800b3a8 2011-02-23        kinaba: #include <cassert>
4fd800b3a8 2011-02-23        kinaba: #include <cstring>
4fd800b3a8 2011-02-23        kinaba: using namespace std;
4fd800b3a8 2011-02-23        kinaba: typedef long long LL;
4fd800b3a8 2011-02-23        kinaba: typedef complex<double> CMP;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: class KiwiJuice { public:
4fd800b3a8 2011-02-23        kinaba: 	int theProfit(int C, vector <int> bottles, vector <int> prices)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		best.clear();
4fd800b3a8 2011-02-23        kinaba: 		best.resize(1<<bottles.size(), -1);
4fd800b3a8 2011-02-23        kinaba: 		return rec((1<<bottles.size())-1, C, bottles, prices);
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	vector<int> best;
4fd800b3a8 2011-02-23        kinaba: 	int rec(int mask, int C, vector<int>& B, const vector<int>& P)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		if( mask == 0 )
4fd800b3a8 2011-02-23        kinaba: 			return 0;
4fd800b3a8 2011-02-23        kinaba: 		if( best[mask] != -1 )
4fd800b3a8 2011-02-23        kinaba: 			return best[mask];
4fd800b3a8 2011-02-23        kinaba: 		int maxSc = 0;
4fd800b3a8 2011-02-23        kinaba: 		for(int subset=mask; subset; subset=((subset-1)&mask)) {
4fd800b3a8 2011-02-23        kinaba: 			int sum = 0;
4fd800b3a8 2011-02-23        kinaba: 			int bin = 0;
4fd800b3a8 2011-02-23        kinaba: 			for(int i=0; i<B.size(); ++i)
4fd800b3a8 2011-02-23        kinaba: 				if( subset & (1<<i) ) {
4fd800b3a8 2011-02-23        kinaba: 					sum += B[i];
4fd800b3a8 2011-02-23        kinaba: 					bin += 1;
4fd800b3a8 2011-02-23        kinaba: 				}
4fd800b3a8 2011-02-23        kinaba: 			int sc = P[C] * (sum/C);
4fd800b3a8 2011-02-23        kinaba: 			if(sum%C) sc += P[sum%C];
4fd800b3a8 2011-02-23        kinaba: 			sc += P[0] *  (bin-((sum/C)+(sum%C?1:0)));
4fd800b3a8 2011-02-23        kinaba: 			sc += rec(mask&~subset, C, B, P);
4fd800b3a8 2011-02-23        kinaba: 			maxSc = max(maxSc, sc);
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 		return best[mask] = maxSc;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: };
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: // BEGIN CUT HERE
4fd800b3a8 2011-02-23        kinaba: #include <ctime>
4fd800b3a8 2011-02-23        kinaba: double start_time; string timer()
4fd800b3a8 2011-02-23        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
4fd800b3a8 2011-02-23        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
4fd800b3a8 2011-02-23        kinaba:  { os << "{ ";
4fd800b3a8 2011-02-23        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
4fd800b3a8 2011-02-23        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
4fd800b3a8 2011-02-23        kinaba: void verify_case(const int& Expected, const int& Received) {
4fd800b3a8 2011-02-23        kinaba:  bool ok = (Expected == Received);
4fd800b3a8 2011-02-23        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
4fd800b3a8 2011-02-23        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
4fd800b3a8 2011-02-23        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
4fd800b3a8 2011-02-23        kinaba: #define END	 verify_case(_, KiwiJuice().theProfit(C, bottles, prices));}
4fd800b3a8 2011-02-23        kinaba: int main(){
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: CASE(0)
4fd800b3a8 2011-02-23        kinaba: 	int C = 10;
4fd800b3a8 2011-02-23        kinaba: 	int bottles_[] = {5, 8};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> bottles(bottles_, bottles_+sizeof(bottles_)/sizeof(*bottles_));
4fd800b3a8 2011-02-23        kinaba: 	int prices_[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> prices(prices_, prices_+sizeof(prices_)/sizeof(*prices_));
4fd800b3a8 2011-02-23        kinaba: 	int _ = 10;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(1)
4fd800b3a8 2011-02-23        kinaba: 	int C = 10;
4fd800b3a8 2011-02-23        kinaba: 	int bottles_[] = {5, 8};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> bottles(bottles_, bottles_+sizeof(bottles_)/sizeof(*bottles_));
4fd800b3a8 2011-02-23        kinaba: 	int prices_[] = {0, 0, 0, 0, 0, 10, 10, 10, 10, 10, 10};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> prices(prices_, prices_+sizeof(prices_)/sizeof(*prices_));
4fd800b3a8 2011-02-23        kinaba: 	int _ = 20;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(2)
4fd800b3a8 2011-02-23        kinaba: 	int C = 10;
4fd800b3a8 2011-02-23        kinaba: 	int bottles_[] = {4, 5, 3, 7};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> bottles(bottles_, bottles_+sizeof(bottles_)/sizeof(*bottles_));
4fd800b3a8 2011-02-23        kinaba: 	int prices_[] = {14, 76, 12, 35, 6, 94, 26, 3, 93, 90, 420};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> prices(prices_, prices_+sizeof(prices_)/sizeof(*prices_));
4fd800b3a8 2011-02-23        kinaba: 	int _ = 625;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(3)
4fd800b3a8 2011-02-23        kinaba: 	int C = 1;
4fd800b3a8 2011-02-23        kinaba: 	int bottles_[] = {0};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> bottles(bottles_, bottles_+sizeof(bottles_)/sizeof(*bottles_));
4fd800b3a8 2011-02-23        kinaba: 	int prices_[] = {1000000, 1000000};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> prices(prices_, prices_+sizeof(prices_)/sizeof(*prices_));
4fd800b3a8 2011-02-23        kinaba: 	int _ = 1000000;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(4)
4fd800b3a8 2011-02-23        kinaba: 	int C = 49;
4fd800b3a8 2011-02-23        kinaba: 	int bottles_[] = {2, 47, 24, 14, 0, 32, 9, 12, 31, 46, 39, 12, 16, 22, 29};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> bottles(bottles_, bottles_+sizeof(bottles_)/sizeof(*bottles_));
4fd800b3a8 2011-02-23        kinaba: 	int prices_[] = {428668, 995687, 128567, 37241, 496916, 238624, 304781, 997819, 85856, 417008,
4fd800b3a8 2011-02-23        kinaba: 398570, 951499, 750349, 333625, 927594, 188616, 942498, 259414, 654344, 354809,
4fd800b3a8 2011-02-23        kinaba: 25303, 226854, 98578, 207140, 305527, 358343, 393213, 256248, 282644, 103327,
4fd800b3a8 2011-02-23        kinaba: 667191, 103402, 609183, 619323, 189127, 518006, 778846, 400460, 128334, 795097,
4fd800b3a8 2011-02-23        kinaba: 605203, 669142, 121825, 934404, 837430, 554265, 610818, 546228, 80784, 949440};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> prices(prices_, prices_+sizeof(prices_)/sizeof(*prices_));
4fd800b3a8 2011-02-23        kinaba: 	int _ = 12873962;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(5)
4fd800b3a8 2011-02-23        kinaba: 	int C = 10;
4fd800b3a8 2011-02-23        kinaba: 	int bottles_[] = {2,3,5};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> bottles(bottles_, bottles_+sizeof(bottles_)/sizeof(*bottles_));
4fd800b3a8 2011-02-23        kinaba: 	  int prices_[] = {0,0,9,9,0,9,0,0,0,0,99};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> prices(prices_, prices_+sizeof(prices_)/sizeof(*prices_));
4fd800b3a8 2011-02-23        kinaba: 	int _ = 99;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: /*
4fd800b3a8 2011-02-23        kinaba: CASE(6)
4fd800b3a8 2011-02-23        kinaba: 	int C = ;
4fd800b3a8 2011-02-23        kinaba: 	int bottles_[] = ;
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> bottles(bottles_, bottles_+sizeof(bottles_)/sizeof(*bottles_));
4fd800b3a8 2011-02-23        kinaba: 	int prices_[] = ;
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> prices(prices_, prices_+sizeof(prices_)/sizeof(*prices_));
4fd800b3a8 2011-02-23        kinaba: 	int _ = ;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: */
4fd800b3a8 2011-02-23        kinaba: }
4fd800b3a8 2011-02-23        kinaba: // END CUT HERE