aca31be9a5 2011-12-24 kinaba: #include <iostream> aca31be9a5 2011-12-24 kinaba: #include <sstream> aca31be9a5 2011-12-24 kinaba: #include <iomanip> aca31be9a5 2011-12-24 kinaba: #include <vector> aca31be9a5 2011-12-24 kinaba: #include <string> aca31be9a5 2011-12-24 kinaba: #include <map> aca31be9a5 2011-12-24 kinaba: #include <set> aca31be9a5 2011-12-24 kinaba: #include <algorithm> aca31be9a5 2011-12-24 kinaba: #include <numeric> aca31be9a5 2011-12-24 kinaba: #include <iterator> aca31be9a5 2011-12-24 kinaba: #include <functional> aca31be9a5 2011-12-24 kinaba: #include <complex> aca31be9a5 2011-12-24 kinaba: #include <queue> aca31be9a5 2011-12-24 kinaba: #include <stack> aca31be9a5 2011-12-24 kinaba: #include <cmath> aca31be9a5 2011-12-24 kinaba: #include <cassert> aca31be9a5 2011-12-24 kinaba: #include <cstring> aca31be9a5 2011-12-24 kinaba: #ifdef __GNUC__ aca31be9a5 2011-12-24 kinaba: #include <ext/hash_map> aca31be9a5 2011-12-24 kinaba: #define unordered_map __gnu_cxx::hash_map aca31be9a5 2011-12-24 kinaba: #else aca31be9a5 2011-12-24 kinaba: #include <unordered_map> aca31be9a5 2011-12-24 kinaba: #endif aca31be9a5 2011-12-24 kinaba: using namespace std; aca31be9a5 2011-12-24 kinaba: typedef long long LL; aca31be9a5 2011-12-24 kinaba: typedef complex<double> CMP; aca31be9a5 2011-12-24 kinaba: aca31be9a5 2011-12-24 kinaba: class P8XGraphBuilder { public: aca31be9a5 2011-12-24 kinaba: int solve(vector <int> scores) aca31be9a5 2011-12-24 kinaba: { aca31be9a5 2011-12-24 kinaba: scores.insert(scores.begin(), 9999999); aca31be9a5 2011-12-24 kinaba: const int N = scores.size(); aca31be9a5 2011-12-24 kinaba: aca31be9a5 2011-12-24 kinaba: int best = 0; aca31be9a5 2011-12-24 kinaba: for(int leaves=1; leaves<N; ++leaves) aca31be9a5 2011-12-24 kinaba: best = max(best, scores[1]*leaves + calc(leaves, N-leaves, scores)); aca31be9a5 2011-12-24 kinaba: return best; aca31be9a5 2011-12-24 kinaba: } aca31be9a5 2011-12-24 kinaba: aca31be9a5 2011-12-24 kinaba: map<pair<int,int>,int> memo; aca31be9a5 2011-12-24 kinaba: int calc(int leaves, int nodes, const vector<int>& scores) aca31be9a5 2011-12-24 kinaba: { aca31be9a5 2011-12-24 kinaba: if( nodes == 1 ) aca31be9a5 2011-12-24 kinaba: return scores[leaves]; aca31be9a5 2011-12-24 kinaba: aca31be9a5 2011-12-24 kinaba: pair<int,int> key(leaves, nodes); aca31be9a5 2011-12-24 kinaba: if( memo.count(key) ) aca31be9a5 2011-12-24 kinaba: return memo[key]; aca31be9a5 2011-12-24 kinaba: aca31be9a5 2011-12-24 kinaba: int best = 0; aca31be9a5 2011-12-24 kinaba: for(int k=1; k<=leaves; ++k) aca31be9a5 2011-12-24 kinaba: best = max(best, scores[k+1] + calc(leaves-k+1, nodes-1, scores)); aca31be9a5 2011-12-24 kinaba: return memo[key] = best; aca31be9a5 2011-12-24 kinaba: } aca31be9a5 2011-12-24 kinaba: }; aca31be9a5 2011-12-24 kinaba: aca31be9a5 2011-12-24 kinaba: // BEGIN CUT HERE aca31be9a5 2011-12-24 kinaba: #include <ctime> aca31be9a5 2011-12-24 kinaba: double start_time; string timer() aca31be9a5 2011-12-24 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } aca31be9a5 2011-12-24 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) aca31be9a5 2011-12-24 kinaba: { os << "{ "; aca31be9a5 2011-12-24 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) aca31be9a5 2011-12-24 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } aca31be9a5 2011-12-24 kinaba: void verify_case(const int& Expected, const int& Received) { aca31be9a5 2011-12-24 kinaba: bool ok = (Expected == Received); aca31be9a5 2011-12-24 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; aca31be9a5 2011-12-24 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } aca31be9a5 2011-12-24 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); aca31be9a5 2011-12-24 kinaba: #define END verify_case(_, P8XGraphBuilder().solve(scores));} aca31be9a5 2011-12-24 kinaba: int main(){ aca31be9a5 2011-12-24 kinaba: aca31be9a5 2011-12-24 kinaba: CASE(0) aca31be9a5 2011-12-24 kinaba: int scores_[] = {1, 3, 0}; aca31be9a5 2011-12-24 kinaba: vector <int> scores(scores_, scores_+sizeof(scores_)/sizeof(*scores_)); aca31be9a5 2011-12-24 kinaba: int _ = 8; aca31be9a5 2011-12-24 kinaba: END aca31be9a5 2011-12-24 kinaba: CASE(1) aca31be9a5 2011-12-24 kinaba: int scores_[] = {0, 0, 0, 10}; aca31be9a5 2011-12-24 kinaba: vector <int> scores(scores_, scores_+sizeof(scores_)/sizeof(*scores_)); aca31be9a5 2011-12-24 kinaba: int _ = 10; aca31be9a5 2011-12-24 kinaba: END aca31be9a5 2011-12-24 kinaba: CASE(2) aca31be9a5 2011-12-24 kinaba: int scores_[] = {1, 2, 3, 4, 5, 6}; aca31be9a5 2011-12-24 kinaba: vector <int> scores(scores_, scores_+sizeof(scores_)/sizeof(*scores_)); aca31be9a5 2011-12-24 kinaba: int _ = 12; aca31be9a5 2011-12-24 kinaba: END aca31be9a5 2011-12-24 kinaba: CASE(3) aca31be9a5 2011-12-24 kinaba: int scores_[] = {5, 0, 0}; aca31be9a5 2011-12-24 kinaba: vector <int> scores(scores_, scores_+sizeof(scores_)/sizeof(*scores_)); aca31be9a5 2011-12-24 kinaba: int _ = 15; aca31be9a5 2011-12-24 kinaba: END aca31be9a5 2011-12-24 kinaba: CASE(4) aca31be9a5 2011-12-24 kinaba: int scores_[] = {1, 3, 2, 5, 3, 7, 5}; aca31be9a5 2011-12-24 kinaba: vector <int> scores(scores_, scores_+sizeof(scores_)/sizeof(*scores_)); aca31be9a5 2011-12-24 kinaba: int _ = 20; aca31be9a5 2011-12-24 kinaba: END aca31be9a5 2011-12-24 kinaba: CASE(5) aca31be9a5 2011-12-24 kinaba: int scores_[] = {1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10}; aca31be9a5 2011-12-24 kinaba: vector <int> scores(scores_, scores_+sizeof(scores_)/sizeof(*scores_)); aca31be9a5 2011-12-24 kinaba: int _ = -1; aca31be9a5 2011-12-24 kinaba: END aca31be9a5 2011-12-24 kinaba: CASE(6) aca31be9a5 2011-12-24 kinaba: int scores_[] = {2}; aca31be9a5 2011-12-24 kinaba: vector <int> scores(scores_, scores_+sizeof(scores_)/sizeof(*scores_)); aca31be9a5 2011-12-24 kinaba: int _ = 4; aca31be9a5 2011-12-24 kinaba: END aca31be9a5 2011-12-24 kinaba: aca31be9a5 2011-12-24 kinaba: } aca31be9a5 2011-12-24 kinaba: // END CUT HERE