bdc8bb3e19 2015-05-13 kinaba: #include <iostream> bdc8bb3e19 2015-05-13 kinaba: #include <sstream> bdc8bb3e19 2015-05-13 kinaba: #include <iomanip> bdc8bb3e19 2015-05-13 kinaba: #include <vector> bdc8bb3e19 2015-05-13 kinaba: #include <string> bdc8bb3e19 2015-05-13 kinaba: #include <map> bdc8bb3e19 2015-05-13 kinaba: #include <set> bdc8bb3e19 2015-05-13 kinaba: #include <algorithm> bdc8bb3e19 2015-05-13 kinaba: #include <numeric> bdc8bb3e19 2015-05-13 kinaba: #include <iterator> bdc8bb3e19 2015-05-13 kinaba: #include <functional> bdc8bb3e19 2015-05-13 kinaba: #include <complex> bdc8bb3e19 2015-05-13 kinaba: #include <queue> bdc8bb3e19 2015-05-13 kinaba: #include <stack> bdc8bb3e19 2015-05-13 kinaba: #include <cmath> bdc8bb3e19 2015-05-13 kinaba: #include <cassert> bdc8bb3e19 2015-05-13 kinaba: #include <tuple> bdc8bb3e19 2015-05-13 kinaba: using namespace std; bdc8bb3e19 2015-05-13 kinaba: typedef long long LL; bdc8bb3e19 2015-05-13 kinaba: typedef complex<double> CMP; bdc8bb3e19 2015-05-13 kinaba: bdc8bb3e19 2015-05-13 kinaba: class ProblemSets { public: bdc8bb3e19 2015-05-13 kinaba: long long maxSets(long long E, long long EM, long long M, long long MH, long long H) bdc8bb3e19 2015-05-13 kinaba: { bdc8bb3e19 2015-05-13 kinaba: LL L=0, R=0x7fffffffffffffffLL; // can make [L,R) bdc8bb3e19 2015-05-13 kinaba: while(R-L>1) { bdc8bb3e19 2015-05-13 kinaba: LL C = L+(R-L)/2; bdc8bb3e19 2015-05-13 kinaba: (can(E,EM,M,MH,H,C) ? L : R) = C; bdc8bb3e19 2015-05-13 kinaba: } bdc8bb3e19 2015-05-13 kinaba: return L; bdc8bb3e19 2015-05-13 kinaba: } bdc8bb3e19 2015-05-13 kinaba: bdc8bb3e19 2015-05-13 kinaba: bool can(long long E, long long EM, long long M, long long MH, long long H, LL nProbs) { bdc8bb3e19 2015-05-13 kinaba: LL eNeed = max(0LL, nProbs-E); bdc8bb3e19 2015-05-13 kinaba: LL mNeed = max(0LL, nProbs-M); bdc8bb3e19 2015-05-13 kinaba: LL hNeed = max(0LL, nProbs-H); bdc8bb3e19 2015-05-13 kinaba: if(EM < eNeed) return false; bdc8bb3e19 2015-05-13 kinaba: EM -= eNeed; bdc8bb3e19 2015-05-13 kinaba: if(MH < hNeed) return false; bdc8bb3e19 2015-05-13 kinaba: MH -= hNeed; bdc8bb3e19 2015-05-13 kinaba: return mNeed <= EM+MH; bdc8bb3e19 2015-05-13 kinaba: } bdc8bb3e19 2015-05-13 kinaba: }; bdc8bb3e19 2015-05-13 kinaba: bdc8bb3e19 2015-05-13 kinaba: // BEGIN CUT HERE bdc8bb3e19 2015-05-13 kinaba: #include <ctime> bdc8bb3e19 2015-05-13 kinaba: double start_time; string timer() bdc8bb3e19 2015-05-13 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } bdc8bb3e19 2015-05-13 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) bdc8bb3e19 2015-05-13 kinaba: { os << "{ "; bdc8bb3e19 2015-05-13 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) bdc8bb3e19 2015-05-13 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } bdc8bb3e19 2015-05-13 kinaba: void verify_case(const long long& Expected, const long long& Received) { bdc8bb3e19 2015-05-13 kinaba: bool ok = (Expected == Received); bdc8bb3e19 2015-05-13 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; bdc8bb3e19 2015-05-13 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } bdc8bb3e19 2015-05-13 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); bdc8bb3e19 2015-05-13 kinaba: #define END verify_case(_, ProblemSets().maxSets(E, EM, M, MH, H));} bdc8bb3e19 2015-05-13 kinaba: int main(){ bdc8bb3e19 2015-05-13 kinaba: bdc8bb3e19 2015-05-13 kinaba: CASE(0) bdc8bb3e19 2015-05-13 kinaba: long long E = 2LL; bdc8bb3e19 2015-05-13 kinaba: long long EM = 2LL; bdc8bb3e19 2015-05-13 kinaba: long long M = 1LL; bdc8bb3e19 2015-05-13 kinaba: long long MH = 2LL; bdc8bb3e19 2015-05-13 kinaba: long long H = 2LL; bdc8bb3e19 2015-05-13 kinaba: long long _ = 3LL; bdc8bb3e19 2015-05-13 kinaba: END bdc8bb3e19 2015-05-13 kinaba: CASE(1) bdc8bb3e19 2015-05-13 kinaba: long long E = 100LL; bdc8bb3e19 2015-05-13 kinaba: long long EM = 100LL; bdc8bb3e19 2015-05-13 kinaba: long long M = 100LL; bdc8bb3e19 2015-05-13 kinaba: long long MH = 0LL; bdc8bb3e19 2015-05-13 kinaba: long long H = 0LL; bdc8bb3e19 2015-05-13 kinaba: long long _ = 0LL; bdc8bb3e19 2015-05-13 kinaba: END bdc8bb3e19 2015-05-13 kinaba: CASE(2) bdc8bb3e19 2015-05-13 kinaba: long long E = 657LL; bdc8bb3e19 2015-05-13 kinaba: long long EM = 657LL; bdc8bb3e19 2015-05-13 kinaba: long long M = 657LL; bdc8bb3e19 2015-05-13 kinaba: long long MH = 657LL; bdc8bb3e19 2015-05-13 kinaba: long long H = 657LL; bdc8bb3e19 2015-05-13 kinaba: long long _ = 1095LL; bdc8bb3e19 2015-05-13 kinaba: END bdc8bb3e19 2015-05-13 kinaba: CASE(3) bdc8bb3e19 2015-05-13 kinaba: long long E = 1LL; bdc8bb3e19 2015-05-13 kinaba: long long EM = 2LL; bdc8bb3e19 2015-05-13 kinaba: long long M = 3LL; bdc8bb3e19 2015-05-13 kinaba: long long MH = 4LL; bdc8bb3e19 2015-05-13 kinaba: long long H = 5LL; bdc8bb3e19 2015-05-13 kinaba: long long _ = 3LL; bdc8bb3e19 2015-05-13 kinaba: END bdc8bb3e19 2015-05-13 kinaba: CASE(4) bdc8bb3e19 2015-05-13 kinaba: long long E = 1000000000000000000LL; bdc8bb3e19 2015-05-13 kinaba: long long EM = 1000000000000000000LL; bdc8bb3e19 2015-05-13 kinaba: long long M = 1000000000000000000LL; bdc8bb3e19 2015-05-13 kinaba: long long MH = 1000000000000000000LL; bdc8bb3e19 2015-05-13 kinaba: long long H = 1000000000000000000LL; bdc8bb3e19 2015-05-13 kinaba: long long _ = 1666666666666666666LL; bdc8bb3e19 2015-05-13 kinaba: END bdc8bb3e19 2015-05-13 kinaba: /* bdc8bb3e19 2015-05-13 kinaba: CASE(5) bdc8bb3e19 2015-05-13 kinaba: long long E = LL; bdc8bb3e19 2015-05-13 kinaba: long long EM = LL; bdc8bb3e19 2015-05-13 kinaba: long long M = LL; bdc8bb3e19 2015-05-13 kinaba: long long MH = LL; bdc8bb3e19 2015-05-13 kinaba: long long H = LL; bdc8bb3e19 2015-05-13 kinaba: long long _ = LL; bdc8bb3e19 2015-05-13 kinaba: END bdc8bb3e19 2015-05-13 kinaba: CASE(6) bdc8bb3e19 2015-05-13 kinaba: long long E = LL; bdc8bb3e19 2015-05-13 kinaba: long long EM = LL; bdc8bb3e19 2015-05-13 kinaba: long long M = LL; bdc8bb3e19 2015-05-13 kinaba: long long MH = LL; bdc8bb3e19 2015-05-13 kinaba: long long H = LL; bdc8bb3e19 2015-05-13 kinaba: long long _ = LL; bdc8bb3e19 2015-05-13 kinaba: END bdc8bb3e19 2015-05-13 kinaba: */ bdc8bb3e19 2015-05-13 kinaba: } bdc8bb3e19 2015-05-13 kinaba: // END CUT HERE