Artifact Content
Not logged in

Artifact a29498ed3efc5921f4b7df521bc3e2295e101ca3


#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 MysticAndCandies { public:
	int minBoxes(int C, int X, vector <int> low, vector <int> high)
	{
		sort(low.begin(), low.end());
		int t1 = 0, c1 = 0;
		while(t1 < X) {
			t1 += low.back();
			c1 += 1;
			low.pop_back();
		}

		sort(high.begin(), high.end());
		int t2 = accumulate(high.begin(), high.end(), 0), c2 = 0;
		while(t2 > C-X) {
			t2 -= high.back();
			c2 += 1;
			high.pop_back();
		}

		return min(c1, c2);
	}
};

// 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(_, MysticAndCandies().minBoxes(C, X, low, high));}
int main(){

CASE(0)
	int C = 15; 
	int X = 12; 
	int low_[] = {1, 2, 3, 4, 5};
	  vector <int> low(low_, low_+sizeof(low_)/sizeof(*low_)); 
	int high_[] = {1, 2, 3, 4, 5};
	  vector <int> high(high_, high_+sizeof(high_)/sizeof(*high_)); 
	int _ = 3; 
END
CASE(1)
	int C = 60; 
	int X = 8; 
	int low_[] = {5, 2, 3};
	  vector <int> low(low_, low_+sizeof(low_)/sizeof(*low_)); 
	int high_[] = {49, 48, 47};
	  vector <int> high(high_, high_+sizeof(high_)/sizeof(*high_)); 
	int _ = 2; 
END
CASE(2)
	int C = 58; 
	int X = 30; 
	int low_[] = {3, 9, 12, 6, 15};
	  vector <int> low(low_, low_+sizeof(low_)/sizeof(*low_)); 
	int high_[] = {8, 12, 20, 8, 15};
	  vector <int> high(high_, high_+sizeof(high_)/sizeof(*high_)); 
	int _ = 2; 
END
CASE(3)
	int C = 207581165; 
	int X = 172146543; 
	int low_[] = {4725448, 2753824, 6019698, 4199708, 4070001, 3589497, 5358499, 3637585, 5393667, 2837466,
2747807, 2918199, 3638042, 5199002, 3072044, 3858909, 3762101, 3657754, 3218704, 3888861,
3195689, 4768935, 3137633, 4124272, 4125056, 6087486, 3632970, 3620489, 2748765, 5917493,
3958996, 3335021, 3517186, 5543440, 2951006, 3403270, 3299481, 3093204, 4092331};
	  vector <int> low(low_, low_+sizeof(low_)/sizeof(*low_)); 
	int high_[] = {5702812, 6805664, 6823687, 5337687, 4286533, 4999849, 6567411, 4563235, 6618139, 6260135,
6249469, 3821449, 5963157, 6385012, 4255959, 5786920, 6112817, 4103918, 6371537, 4231698,
3409172, 6806782, 5623563, 4511221, 6407338, 6491490, 5209517, 6076093, 6530132, 6111464,
5833839, 6253088, 5595160, 6236805, 5772388, 5285713, 5617002, 4650978, 5234740};
	  vector <int> high(high_, high_+sizeof(high_)/sizeof(*high_)); 
	int _ = 31; 
END
CASE(4)
	int C = 43873566; 
	int X = 32789748; 
	int low_[] = {2053198, 2175819, 4260803, 1542497, 1418952, 5000015, 1381849, 2462882, 6466891, 1827580, 6943641, 5775477};
	  vector <int> low(low_, low_+sizeof(low_)/sizeof(*low_)); 
	int high_[] = {2827461, 3726335, 5410505, 4781355, 4925909, 5621160, 7325774, 5025476, 7876037, 8072075, 6979462, 6647628};
	  vector <int> high(high_, high_+sizeof(high_)/sizeof(*high_)); 
	int _ = 7; 
END
/*
CASE(5)
	int C = ; 
	int X = ; 
	int low_[] = ;
	  vector <int> low(low_, low_+sizeof(low_)/sizeof(*low_)); 
	int high_[] = ;
	  vector <int> high(high_, high_+sizeof(high_)/sizeof(*high_)); 
	int _ = ; 
END
CASE(6)
	int C = ; 
	int X = ; 
	int low_[] = ;
	  vector <int> low(low_, low_+sizeof(low_)/sizeof(*low_)); 
	int high_[] = ;
	  vector <int> high(high_, high_+sizeof(high_)/sizeof(*high_)); 
	int _ = ; 
END
*/
}
// END CUT HERE