42f877f59c 2012-12-21 kinaba: #include <iostream> 42f877f59c 2012-12-21 kinaba: #include <sstream> 42f877f59c 2012-12-21 kinaba: #include <iomanip> 42f877f59c 2012-12-21 kinaba: #include <vector> 42f877f59c 2012-12-21 kinaba: #include <string> 42f877f59c 2012-12-21 kinaba: #include <map> 42f877f59c 2012-12-21 kinaba: #include <set> 42f877f59c 2012-12-21 kinaba: #include <algorithm> 42f877f59c 2012-12-21 kinaba: #include <numeric> 42f877f59c 2012-12-21 kinaba: #include <iterator> 42f877f59c 2012-12-21 kinaba: #include <functional> 42f877f59c 2012-12-21 kinaba: #include <complex> 42f877f59c 2012-12-21 kinaba: #include <queue> 42f877f59c 2012-12-21 kinaba: #include <stack> 42f877f59c 2012-12-21 kinaba: #include <cmath> 42f877f59c 2012-12-21 kinaba: #include <cassert> 42f877f59c 2012-12-21 kinaba: using namespace std; 42f877f59c 2012-12-21 kinaba: typedef long long LL; 42f877f59c 2012-12-21 kinaba: typedef long double LD; 42f877f59c 2012-12-21 kinaba: typedef complex<LD> CMP; 42f877f59c 2012-12-21 kinaba: 42f877f59c 2012-12-21 kinaba: class MonstersValley { public: 42f877f59c 2012-12-21 kinaba: int minimumPrice(vector<long long> dread, vector <int> price) 42f877f59c 2012-12-21 kinaba: { 42f877f59c 2012-12-21 kinaba: const int N = dread.size(); 42f877f59c 2012-12-21 kinaba: 42f877f59c 2012-12-21 kinaba: map<int, LL> p2maxd; 42f877f59c 2012-12-21 kinaba: p2maxd[0] = 0; 42f877f59c 2012-12-21 kinaba: 42f877f59c 2012-12-21 kinaba: for(int i=0; i<N; ++i) { 42f877f59c 2012-12-21 kinaba: map<int,LL> neo; 42f877f59c 2012-12-21 kinaba: for(map<int,LL>::iterator it=p2maxd.begin(); it!=p2maxd.end(); ++it) 42f877f59c 2012-12-21 kinaba: { 42f877f59c 2012-12-21 kinaba: int p = it->first; 42f877f59c 2012-12-21 kinaba: LL md = it->second; 42f877f59c 2012-12-21 kinaba: if( md >= dread[i] ) 42f877f59c 2012-12-21 kinaba: neo[p] = max(neo[p], md); 42f877f59c 2012-12-21 kinaba: p += price[i]; 42f877f59c 2012-12-21 kinaba: md += dread[i]; 42f877f59c 2012-12-21 kinaba: neo[p] = max(neo[p], md); 42f877f59c 2012-12-21 kinaba: } 42f877f59c 2012-12-21 kinaba: p2maxd.swap(neo); 42f877f59c 2012-12-21 kinaba: } 42f877f59c 2012-12-21 kinaba: 42f877f59c 2012-12-21 kinaba: return p2maxd.begin()->first; 42f877f59c 2012-12-21 kinaba: } 42f877f59c 2012-12-21 kinaba: }; 42f877f59c 2012-12-21 kinaba: 42f877f59c 2012-12-21 kinaba: // BEGIN CUT HERE 42f877f59c 2012-12-21 kinaba: #include <ctime> 42f877f59c 2012-12-21 kinaba: double start_time; string timer() 42f877f59c 2012-12-21 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 42f877f59c 2012-12-21 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 42f877f59c 2012-12-21 kinaba: { os << "{ "; 42f877f59c 2012-12-21 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 42f877f59c 2012-12-21 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 42f877f59c 2012-12-21 kinaba: void verify_case(const int& Expected, const int& Received) { 42f877f59c 2012-12-21 kinaba: bool ok = (Expected == Received); 42f877f59c 2012-12-21 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 42f877f59c 2012-12-21 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 42f877f59c 2012-12-21 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 42f877f59c 2012-12-21 kinaba: #define END verify_case(_, MonstersValley().minimumPrice(dread, price));} 42f877f59c 2012-12-21 kinaba: int main(){ 42f877f59c 2012-12-21 kinaba: 42f877f59c 2012-12-21 kinaba: CASE(0) 42f877f59c 2012-12-21 kinaba: long long dread_[] = {8, 5, 10}; 42f877f59c 2012-12-21 kinaba: vector<long long> dread(dread_, dread_+sizeof(dread_)/sizeof(*dread_)); 42f877f59c 2012-12-21 kinaba: int price_[] = {1, 1, 2}; 42f877f59c 2012-12-21 kinaba: vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); 42f877f59c 2012-12-21 kinaba: int _ = 2; 42f877f59c 2012-12-21 kinaba: END 42f877f59c 2012-12-21 kinaba: CASE(0) 42f877f59c 2012-12-21 kinaba: long long dread_[] = {1, 1}; 42f877f59c 2012-12-21 kinaba: vector<long long> dread(dread_, dread_+sizeof(dread_)/sizeof(*dread_)); 42f877f59c 2012-12-21 kinaba: int price_[] = {1, 1}; 42f877f59c 2012-12-21 kinaba: vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); 42f877f59c 2012-12-21 kinaba: int _ = 1; 42f877f59c 2012-12-21 kinaba: END 42f877f59c 2012-12-21 kinaba: CASE(1) 42f877f59c 2012-12-21 kinaba: long long dread_[] = {1, 2, 4, 1000000000}; 42f877f59c 2012-12-21 kinaba: vector<long long> dread(dread_, dread_+sizeof(dread_)/sizeof(*dread_)); 42f877f59c 2012-12-21 kinaba: int price_[] = {1, 1, 1, 2}; 42f877f59c 2012-12-21 kinaba: vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); 42f877f59c 2012-12-21 kinaba: int _ = 5; 42f877f59c 2012-12-21 kinaba: END 42f877f59c 2012-12-21 kinaba: CASE(2) 42f877f59c 2012-12-21 kinaba: long long dread_[] = {200, 107, 105, 206, 307, 400}; 42f877f59c 2012-12-21 kinaba: vector<long long> dread(dread_, dread_+sizeof(dread_)/sizeof(*dread_)); 42f877f59c 2012-12-21 kinaba: int price_[] = {1, 2, 1, 1, 1, 2}; 42f877f59c 2012-12-21 kinaba: vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); 42f877f59c 2012-12-21 kinaba: int _ = 2; 42f877f59c 2012-12-21 kinaba: END 42f877f59c 2012-12-21 kinaba: CASE(3) 42f877f59c 2012-12-21 kinaba: long long dread_[] = {5216, 12512, 613, 1256, 66, 17202, 30000, 23512, 2125, 33333}; 42f877f59c 2012-12-21 kinaba: vector<long long> dread(dread_, dread_+sizeof(dread_)/sizeof(*dread_)); 42f877f59c 2012-12-21 kinaba: int price_[] = {2, 2, 1, 1, 1, 1, 2, 1, 2, 1}; 42f877f59c 2012-12-21 kinaba: vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); 42f877f59c 2012-12-21 kinaba: int _ = 5; 42f877f59c 2012-12-21 kinaba: END 42f877f59c 2012-12-21 kinaba: /* 42f877f59c 2012-12-21 kinaba: CASE(4) 42f877f59c 2012-12-21 kinaba: long long dread_[] = ; 42f877f59c 2012-12-21 kinaba: vector<long long> dread(dread_, dread_+sizeof(dread_)/sizeof(*dread_)); 42f877f59c 2012-12-21 kinaba: int price_[] = ; 42f877f59c 2012-12-21 kinaba: vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); 42f877f59c 2012-12-21 kinaba: int _ = ; 42f877f59c 2012-12-21 kinaba: END 42f877f59c 2012-12-21 kinaba: CASE(5) 42f877f59c 2012-12-21 kinaba: long long dread_[] = ; 42f877f59c 2012-12-21 kinaba: vector<long long> dread(dread_, dread_+sizeof(dread_)/sizeof(*dread_)); 42f877f59c 2012-12-21 kinaba: int price_[] = ; 42f877f59c 2012-12-21 kinaba: vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); 42f877f59c 2012-12-21 kinaba: int _ = ; 42f877f59c 2012-12-21 kinaba: END 42f877f59c 2012-12-21 kinaba: */ 42f877f59c 2012-12-21 kinaba: } 42f877f59c 2012-12-21 kinaba: // END CUT HERE