7325c885f1 2013-06-18        kinaba: #include <iostream>
7325c885f1 2013-06-18        kinaba: #include <sstream>
7325c885f1 2013-06-18        kinaba: #include <iomanip>
7325c885f1 2013-06-18        kinaba: #include <vector>
7325c885f1 2013-06-18        kinaba: #include <string>
7325c885f1 2013-06-18        kinaba: #include <map>
7325c885f1 2013-06-18        kinaba: #include <set>
7325c885f1 2013-06-18        kinaba: #include <algorithm>
7325c885f1 2013-06-18        kinaba: #include <numeric>
7325c885f1 2013-06-18        kinaba: #include <iterator>
7325c885f1 2013-06-18        kinaba: #include <functional>
7325c885f1 2013-06-18        kinaba: #include <complex>
7325c885f1 2013-06-18        kinaba: #include <queue>
7325c885f1 2013-06-18        kinaba: #include <stack>
7325c885f1 2013-06-18        kinaba: #include <cmath>
7325c885f1 2013-06-18        kinaba: #include <cassert>
7325c885f1 2013-06-18        kinaba: using namespace std;
7325c885f1 2013-06-18        kinaba: typedef long long LL;
7325c885f1 2013-06-18        kinaba: typedef long double LD;
7325c885f1 2013-06-18        kinaba: typedef complex<double> CMP;
7325c885f1 2013-06-18        kinaba: 
7325c885f1 2013-06-18        kinaba: class SpaceWarDiv1 { public:
7325c885f1 2013-06-18        kinaba: 	long long minimalFatigue(vector <int> magicalGirlStrength, vector <int> enemyStrength, vector<long long> enemyCount)
7325c885f1 2013-06-18        kinaba: 	{
7325c885f1 2013-06-18        kinaba: 		int M = *max_element(magicalGirlStrength.begin(), magicalGirlStrength.end());
7325c885f1 2013-06-18        kinaba: 		int E = *max_element(enemyStrength.begin(), enemyStrength.end());
7325c885f1 2013-06-18        kinaba: 		if(M<E)
7325c885f1 2013-06-18        kinaba: 			return -1;
7325c885f1 2013-06-18        kinaba: 		sort(magicalGirlStrength.rbegin(), magicalGirlStrength.rend());
7325c885f1 2013-06-18        kinaba: 		vector< pair<int,LL> > e;
7325c885f1 2013-06-18        kinaba: 		for(int i=0; i<enemyStrength.size(); ++i)
7325c885f1 2013-06-18        kinaba: 			e.push_back(make_pair(enemyStrength[i], enemyCount[i]));
7325c885f1 2013-06-18        kinaba: 		sort(e.rbegin(), e.rend());
7325c885f1 2013-06-18        kinaba: 
7325c885f1 2013-06-18        kinaba: 		LL L=0, R=accumulate(enemyCount.begin(), enemyCount.end(), 0LL); // (L,R)
7325c885f1 2013-06-18        kinaba: 		while(R-L>1) {
7325c885f1 2013-06-18        kinaba: 			LL C = (L+R)/2;
7325c885f1 2013-06-18        kinaba: 			(possible(magicalGirlStrength, e, C) ? R : L) = C;
7325c885f1 2013-06-18        kinaba: 		}
7325c885f1 2013-06-18        kinaba: 		return R;
7325c885f1 2013-06-18        kinaba: 	}
7325c885f1 2013-06-18        kinaba: 
7325c885f1 2013-06-18        kinaba: 	bool possible(const vector<int>& m, const vector<pair<int,LL> >& e, LL F)
7325c885f1 2013-06-18        kinaba: 	{
7325c885f1 2013-06-18        kinaba: 		int ei = 0;
7325c885f1 2013-06-18        kinaba: 		LL  eC = e[ei].second;
7325c885f1 2013-06-18        kinaba: 		for(int i=0; i<m.size() && ei<e.size(); ++i)
7325c885f1 2013-06-18        kinaba: 		{
7325c885f1 2013-06-18        kinaba: 			if(e[ei].first > m[i])
7325c885f1 2013-06-18        kinaba: 				return false;
7325c885f1 2013-06-18        kinaba: 
7325c885f1 2013-06-18        kinaba: 			for(LL p = F; p; ) {
7325c885f1 2013-06-18        kinaba: 				if(eC > p) {
7325c885f1 2013-06-18        kinaba: 					eC -= p;
7325c885f1 2013-06-18        kinaba: 					p = 0;
7325c885f1 2013-06-18        kinaba: 				}
7325c885f1 2013-06-18        kinaba: 				else {
7325c885f1 2013-06-18        kinaba: 					++ei;
7325c885f1 2013-06-18        kinaba: 					if(ei == e.size())
7325c885f1 2013-06-18        kinaba: 						return true;
7325c885f1 2013-06-18        kinaba: 					p -= eC;
7325c885f1 2013-06-18        kinaba: 					eC = e[ei].second;
7325c885f1 2013-06-18        kinaba: 				}
7325c885f1 2013-06-18        kinaba: 			}
7325c885f1 2013-06-18        kinaba: 		}
7325c885f1 2013-06-18        kinaba: 		return (ei == e.size());
7325c885f1 2013-06-18        kinaba: 	}
7325c885f1 2013-06-18        kinaba: };
7325c885f1 2013-06-18        kinaba: 
7325c885f1 2013-06-18        kinaba: // BEGIN CUT HERE
7325c885f1 2013-06-18        kinaba: #include <ctime>
7325c885f1 2013-06-18        kinaba: double start_time; string timer()
7325c885f1 2013-06-18        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
7325c885f1 2013-06-18        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
7325c885f1 2013-06-18        kinaba:  { os << "{ ";
7325c885f1 2013-06-18        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
7325c885f1 2013-06-18        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
7325c885f1 2013-06-18        kinaba: void verify_case(const long long& Expected, const long long& Received) {
7325c885f1 2013-06-18        kinaba:  bool ok = (Expected == Received);
7325c885f1 2013-06-18        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
7325c885f1 2013-06-18        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
7325c885f1 2013-06-18        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
7325c885f1 2013-06-18        kinaba: #define END	 verify_case(_, SpaceWarDiv1().minimalFatigue(magicalGirlStrength, enemyStrength, enemyCount));}
7325c885f1 2013-06-18        kinaba: int main(){
7325c885f1 2013-06-18        kinaba: 
7325c885f1 2013-06-18        kinaba: CASE(0)
7325c885f1 2013-06-18        kinaba: 	int magicalGirlStrength_[] = {2, 3, 5};
7325c885f1 2013-06-18        kinaba: 	  vector <int> magicalGirlStrength(magicalGirlStrength_, magicalGirlStrength_+sizeof(magicalGirlStrength_)/sizeof(*magicalGirlStrength_));
7325c885f1 2013-06-18        kinaba: 	int enemyStrength_[] = {1, 3, 4};
7325c885f1 2013-06-18        kinaba: 	  vector <int> enemyStrength(enemyStrength_, enemyStrength_+sizeof(enemyStrength_)/sizeof(*enemyStrength_));
7325c885f1 2013-06-18        kinaba: 	long long enemyCount_[] = {2, 9, 4};
7325c885f1 2013-06-18        kinaba: 	  vector<long long> enemyCount(enemyCount_, enemyCount_+sizeof(enemyCount_)/sizeof(*enemyCount_));
7325c885f1 2013-06-18        kinaba: 	long long _ = 7LL;
7325c885f1 2013-06-18        kinaba: END
7325c885f1 2013-06-18        kinaba: CASE(1)
7325c885f1 2013-06-18        kinaba: 	int magicalGirlStrength_[] = {2, 3, 5};
7325c885f1 2013-06-18        kinaba: 	  vector <int> magicalGirlStrength(magicalGirlStrength_, magicalGirlStrength_+sizeof(magicalGirlStrength_)/sizeof(*magicalGirlStrength_));
7325c885f1 2013-06-18        kinaba: 	int enemyStrength_[] = {1, 1, 2};
7325c885f1 2013-06-18        kinaba: 	  vector <int> enemyStrength(enemyStrength_, enemyStrength_+sizeof(enemyStrength_)/sizeof(*enemyStrength_));
7325c885f1 2013-06-18        kinaba: 	long long enemyCount_[] = {2, 9, 4};
7325c885f1 2013-06-18        kinaba: 	  vector<long long> enemyCount(enemyCount_, enemyCount_+sizeof(enemyCount_)/sizeof(*enemyCount_));
7325c885f1 2013-06-18        kinaba: 	long long _ = 5LL;
7325c885f1 2013-06-18        kinaba: END
7325c885f1 2013-06-18        kinaba: CASE(2)
7325c885f1 2013-06-18        kinaba: 	int magicalGirlStrength_[] = {14, 6, 22};
7325c885f1 2013-06-18        kinaba: 	  vector <int> magicalGirlStrength(magicalGirlStrength_, magicalGirlStrength_+sizeof(magicalGirlStrength_)/sizeof(*magicalGirlStrength_));
7325c885f1 2013-06-18        kinaba: 	int enemyStrength_[] = {8, 33};
7325c885f1 2013-06-18        kinaba: 	  vector <int> enemyStrength(enemyStrength_, enemyStrength_+sizeof(enemyStrength_)/sizeof(*enemyStrength_));
7325c885f1 2013-06-18        kinaba: 	long long enemyCount_[] = {9, 1};
7325c885f1 2013-06-18        kinaba: 	  vector<long long> enemyCount(enemyCount_, enemyCount_+sizeof(enemyCount_)/sizeof(*enemyCount_));
7325c885f1 2013-06-18        kinaba: 	long long _ = -1LL;
7325c885f1 2013-06-18        kinaba: END
7325c885f1 2013-06-18        kinaba: CASE(3)
7325c885f1 2013-06-18        kinaba: 	int magicalGirlStrength_[] = {869, 249, 599, 144, 929, 748, 665, 37, 313, 99, 33, 437, 308, 137, 665, 834, 955, 958, 613, 417};
7325c885f1 2013-06-18        kinaba: 	  vector <int> magicalGirlStrength(magicalGirlStrength_, magicalGirlStrength_+sizeof(magicalGirlStrength_)/sizeof(*magicalGirlStrength_));
7325c885f1 2013-06-18        kinaba: 	int enemyStrength_[] = {789, 57, 684, 741, 128, 794, 542, 367, 937, 739, 568, 872, 127, 261, 103, 763, 864, 360, 618, 307};
7325c885f1 2013-06-18        kinaba: 	  vector <int> enemyStrength(enemyStrength_, enemyStrength_+sizeof(enemyStrength_)/sizeof(*enemyStrength_));
7325c885f1 2013-06-18        kinaba: 	long long enemyCount_[] = {20626770196420, 45538527263992, 52807114957507, 17931716090785, 65032910980630, 88711853198687, 26353250637092,
7325c885f1 2013-06-18        kinaba:  61272534748707, 89294362230771, 52058590967576, 60568594469453, 23772707032338, 43019142889727, 39566072849912,
7325c885f1 2013-06-18        kinaba:  78870845257173, 68135668032761, 36844201017584, 10133804676521, 6275847412927, 37492167783296};
7325c885f1 2013-06-18        kinaba: 	  vector<long long> enemyCount(enemyCount_, enemyCount_+sizeof(enemyCount_)/sizeof(*enemyCount_));
7325c885f1 2013-06-18        kinaba: 	long long _ = 75030497287405LL;
7325c885f1 2013-06-18        kinaba: END
7325c885f1 2013-06-18        kinaba: CASE(4)
7325c885f1 2013-06-18        kinaba: int magicalGirlStrength_[] = {66,16,15,85,98,82,100,21,87,21,63,48,22,82,49,91,69,85,82,100,70,40,77,53,36,8,54,26,35,7,36,74,36,70,10,30,89,14,14,64,89,87,68,40,16,46,28,75,43,10};
7325c885f1 2013-06-18        kinaba: 	  vector <int> magicalGirlStrength(magicalGirlStrength_, magicalGirlStrength_+sizeof(magicalGirlStrength_)/sizeof(*magicalGirlStrength_));
7325c885f1 2013-06-18        kinaba: 	  int enemyStrength_[] = {1};
7325c885f1 2013-06-18        kinaba: 	  vector <int> enemyStrength(enemyStrength_, enemyStrength_+sizeof(enemyStrength_)/sizeof(*enemyStrength_));
7325c885f1 2013-06-18        kinaba: 	  long long enemyCount_[] = {100000000000LL};
7325c885f1 2013-06-18        kinaba: 	  vector<long long> enemyCount(enemyCount_, enemyCount_+sizeof(enemyCount_)/sizeof(*enemyCount_));
7325c885f1 2013-06-18        kinaba: 	long long _ = -1LL;
7325c885f1 2013-06-18        kinaba: END
7325c885f1 2013-06-18        kinaba: /*
7325c885f1 2013-06-18        kinaba: CASE(5)
7325c885f1 2013-06-18        kinaba: 	int magicalGirlStrength_[] = ;
7325c885f1 2013-06-18        kinaba: 	  vector <int> magicalGirlStrength(magicalGirlStrength_, magicalGirlStrength_+sizeof(magicalGirlStrength_)/sizeof(*magicalGirlStrength_));
7325c885f1 2013-06-18        kinaba: 	int enemyStrength_[] = ;
7325c885f1 2013-06-18        kinaba: 	  vector <int> enemyStrength(enemyStrength_, enemyStrength_+sizeof(enemyStrength_)/sizeof(*enemyStrength_));
7325c885f1 2013-06-18        kinaba: 	long long enemyCount_[] = ;
7325c885f1 2013-06-18        kinaba: 	  vector<long long> enemyCount(enemyCount_, enemyCount_+sizeof(enemyCount_)/sizeof(*enemyCount_));
7325c885f1 2013-06-18        kinaba: 	long long _ = LL;
7325c885f1 2013-06-18        kinaba: END
7325c885f1 2013-06-18        kinaba: 	*/
7325c885f1 2013-06-18        kinaba: }
7325c885f1 2013-06-18        kinaba: // END CUT HERE