5f2714f57a 2012-02-18 kinaba: #include <iostream> 5f2714f57a 2012-02-18 kinaba: #include <sstream> 5f2714f57a 2012-02-18 kinaba: #include <iomanip> 5f2714f57a 2012-02-18 kinaba: #include <vector> 5f2714f57a 2012-02-18 kinaba: #include <string> 5f2714f57a 2012-02-18 kinaba: #include <map> 5f2714f57a 2012-02-18 kinaba: #include <set> 5f2714f57a 2012-02-18 kinaba: #include <algorithm> 5f2714f57a 2012-02-18 kinaba: #include <numeric> 5f2714f57a 2012-02-18 kinaba: #include <iterator> 5f2714f57a 2012-02-18 kinaba: #include <functional> 5f2714f57a 2012-02-18 kinaba: #include <complex> 5f2714f57a 2012-02-18 kinaba: #include <queue> 5f2714f57a 2012-02-18 kinaba: #include <stack> 5f2714f57a 2012-02-18 kinaba: #include <cmath> 5f2714f57a 2012-02-18 kinaba: #include <cassert> 5f2714f57a 2012-02-18 kinaba: #include <cstring> 5f2714f57a 2012-02-18 kinaba: #ifdef __GNUC__ 5f2714f57a 2012-02-18 kinaba: #include <ext/hash_map> 5f2714f57a 2012-02-18 kinaba: #define unordered_map __gnu_cxx::hash_map 5f2714f57a 2012-02-18 kinaba: #else 5f2714f57a 2012-02-18 kinaba: #include <unordered_map> 5f2714f57a 2012-02-18 kinaba: #endif 5f2714f57a 2012-02-18 kinaba: using namespace std; 5f2714f57a 2012-02-18 kinaba: typedef long long LL; 5f2714f57a 2012-02-18 kinaba: typedef complex<double> CMP; 5f2714f57a 2012-02-18 kinaba: 5f2714f57a 2012-02-18 kinaba: class DengklekMakingChains { public: 5f2714f57a 2012-02-18 kinaba: int maxBeauty(vector <string> chains) 5f2714f57a 2012-02-18 kinaba: { 5f2714f57a 2012-02-18 kinaba: int best = 0; 5f2714f57a 2012-02-18 kinaba: for(int C=0; C<chains.size(); ++C) { 5f2714f57a 2012-02-18 kinaba: best = max(best, single(chains[C])); 5f2714f57a 2012-02-18 kinaba: } 5f2714f57a 2012-02-18 kinaba: 5f2714f57a 2012-02-18 kinaba: for(int L=0; L<chains.size(); ++L) 5f2714f57a 2012-02-18 kinaba: { 5f2714f57a 2012-02-18 kinaba: int vl = c__( string(chains[L].rbegin(), chains[L].rend()) ); 5f2714f57a 2012-02-18 kinaba: for(int R=0; R<chains.size(); ++R) if( L != R ) 5f2714f57a 2012-02-18 kinaba: { 5f2714f57a 2012-02-18 kinaba: int v = vl + c__(chains[R]); 5f2714f57a 2012-02-18 kinaba: for(int C=0; C<chains.size(); ++C) if(C!=L && C!=R) 5f2714f57a 2012-02-18 kinaba: v += all(chains[C]); 5f2714f57a 2012-02-18 kinaba: best = max(best, v); 5f2714f57a 2012-02-18 kinaba: } 5f2714f57a 2012-02-18 kinaba: } 5f2714f57a 2012-02-18 kinaba: return best; 5f2714f57a 2012-02-18 kinaba: } 5f2714f57a 2012-02-18 kinaba: 5f2714f57a 2012-02-18 kinaba: int single(const string& s) 5f2714f57a 2012-02-18 kinaba: { 5f2714f57a 2012-02-18 kinaba: int best = 0; 5f2714f57a 2012-02-18 kinaba: for(int i=0; i<3; ++i) 5f2714f57a 2012-02-18 kinaba: for(int k=i+1; k<=3; ++k) { 5f2714f57a 2012-02-18 kinaba: int v = 0; 5f2714f57a 2012-02-18 kinaba: for(int a=i; a<k; ++a) 5f2714f57a 2012-02-18 kinaba: if(s[a]!='.') 5f2714f57a 2012-02-18 kinaba: v += s[a]-'0'; 5f2714f57a 2012-02-18 kinaba: else 5f2714f57a 2012-02-18 kinaba: goto next; 5f2714f57a 2012-02-18 kinaba: best = max(best, v); 5f2714f57a 2012-02-18 kinaba: next:; 5f2714f57a 2012-02-18 kinaba: } 5f2714f57a 2012-02-18 kinaba: return best; 5f2714f57a 2012-02-18 kinaba: } 5f2714f57a 2012-02-18 kinaba: int all(const string& s) 5f2714f57a 2012-02-18 kinaba: { 5f2714f57a 2012-02-18 kinaba: int v = 0; 5f2714f57a 2012-02-18 kinaba: for(int a=0; a<3; ++a) 5f2714f57a 2012-02-18 kinaba: if(s[a]!='.') 5f2714f57a 2012-02-18 kinaba: v += s[a]-'0'; 5f2714f57a 2012-02-18 kinaba: else 5f2714f57a 2012-02-18 kinaba: return 0; 5f2714f57a 2012-02-18 kinaba: return v; 5f2714f57a 2012-02-18 kinaba: } 5f2714f57a 2012-02-18 kinaba: int c__(const string& s) 5f2714f57a 2012-02-18 kinaba: { 5f2714f57a 2012-02-18 kinaba: int v = 0; 5f2714f57a 2012-02-18 kinaba: for(int a=0; a<3; ++a) 5f2714f57a 2012-02-18 kinaba: if(s[a]!='.') 5f2714f57a 2012-02-18 kinaba: v += s[a]-'0'; 5f2714f57a 2012-02-18 kinaba: else 5f2714f57a 2012-02-18 kinaba: return v; 5f2714f57a 2012-02-18 kinaba: return v; 5f2714f57a 2012-02-18 kinaba: } 5f2714f57a 2012-02-18 kinaba: }; 5f2714f57a 2012-02-18 kinaba: 5f2714f57a 2012-02-18 kinaba: // BEGIN CUT HERE 5f2714f57a 2012-02-18 kinaba: #include <ctime> 5f2714f57a 2012-02-18 kinaba: double start_time; string timer() 5f2714f57a 2012-02-18 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 5f2714f57a 2012-02-18 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 5f2714f57a 2012-02-18 kinaba: { os << "{ "; 5f2714f57a 2012-02-18 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 5f2714f57a 2012-02-18 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 5f2714f57a 2012-02-18 kinaba: void verify_case(const int& Expected, const int& Received) { 5f2714f57a 2012-02-18 kinaba: bool ok = (Expected == Received); 5f2714f57a 2012-02-18 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 5f2714f57a 2012-02-18 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 5f2714f57a 2012-02-18 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 5f2714f57a 2012-02-18 kinaba: #define END verify_case(_, DengklekMakingChains().maxBeauty(chains));} 5f2714f57a 2012-02-18 kinaba: int main(){ 5f2714f57a 2012-02-18 kinaba: 5f2714f57a 2012-02-18 kinaba: CASE(0) 5f2714f57a 2012-02-18 kinaba: string chains_[] = {".15", "7..", "402", "..3"}; 5f2714f57a 2012-02-18 kinaba: vector <string> chains(chains_, chains_+sizeof(chains_)/sizeof(*chains_)); 5f2714f57a 2012-02-18 kinaba: int _ = 19; 5f2714f57a 2012-02-18 kinaba: // .15 402 7.. 5f2714f57a 2012-02-18 kinaba: END 5f2714f57a 2012-02-18 kinaba: CASE(1) 5f2714f57a 2012-02-18 kinaba: string chains_[] = {"..1", "7..", "567", "24.", "8..", "234"}; 5f2714f57a 2012-02-18 kinaba: vector <string> chains(chains_, chains_+sizeof(chains_)/sizeof(*chains_)); 5f2714f57a 2012-02-18 kinaba: int _ = 36; 5f2714f57a 2012-02-18 kinaba: // ..1 567 234 8.. 5f2714f57a 2012-02-18 kinaba: END 5f2714f57a 2012-02-18 kinaba: CASE(2) 5f2714f57a 2012-02-18 kinaba: string chains_[] = {"...", "..."}; 5f2714f57a 2012-02-18 kinaba: vector <string> chains(chains_, chains_+sizeof(chains_)/sizeof(*chains_)); 5f2714f57a 2012-02-18 kinaba: int _ = 0; 5f2714f57a 2012-02-18 kinaba: END 5f2714f57a 2012-02-18 kinaba: CASE(3) 5f2714f57a 2012-02-18 kinaba: string chains_[] = {"16.", "9.8", ".24", "52.", "3.1", "532", "4.4", "111"}; 5f2714f57a 2012-02-18 kinaba: vector <string> chains(chains_, chains_+sizeof(chains_)/sizeof(*chains_)); 5f2714f57a 2012-02-18 kinaba: int _ = 28; 5f2714f57a 2012-02-18 kinaba: // .24 532 111 9.8 5f2714f57a 2012-02-18 kinaba: // or 5f2714f57a 2012-02-18 kinaba: // 9.8 532 111 16. 5f2714f57a 2012-02-18 kinaba: END 5f2714f57a 2012-02-18 kinaba: CASE(4) 5f2714f57a 2012-02-18 kinaba: string chains_[] = {"..1", "3..", "2..", ".7."}; 5f2714f57a 2012-02-18 kinaba: vector <string> chains(chains_, chains_+sizeof(chains_)/sizeof(*chains_)); 5f2714f57a 2012-02-18 kinaba: int _ = 7; 5f2714f57a 2012-02-18 kinaba: // .7. 5f2714f57a 2012-02-18 kinaba: END 5f2714f57a 2012-02-18 kinaba: CASE(5) 5f2714f57a 2012-02-18 kinaba: string chains_[] = {"412", "..7", ".58", "7.8", "32.", "6..", "351", "3.9", "985", "...", ".46"}; 5f2714f57a 2012-02-18 kinaba: vector <string> chains(chains_, chains_+sizeof(chains_)/sizeof(*chains_)); 5f2714f57a 2012-02-18 kinaba: int _ = 58; 5f2714f57a 2012-02-18 kinaba: // .58 412 351 985 7.8 5f2714f57a 2012-02-18 kinaba: END 5f2714f57a 2012-02-18 kinaba: CASE(6) 5f2714f57a 2012-02-18 kinaba: string chains_[] = {"9..", "..9"}; 5f2714f57a 2012-02-18 kinaba: vector <string> chains(chains_, chains_+sizeof(chains_)/sizeof(*chains_)); 5f2714f57a 2012-02-18 kinaba: int _ = 18; 5f2714f57a 2012-02-18 kinaba: END 5f2714f57a 2012-02-18 kinaba: CASE(7) 5f2714f57a 2012-02-18 kinaba: string chains_[] = {"..1"}; 5f2714f57a 2012-02-18 kinaba: vector <string> chains(chains_, chains_+sizeof(chains_)/sizeof(*chains_)); 5f2714f57a 2012-02-18 kinaba: int _ = 1; 5f2714f57a 2012-02-18 kinaba: END 5f2714f57a 2012-02-18 kinaba: } 5f2714f57a 2012-02-18 kinaba: // END CUT HERE