3d2bcff745 2011-12-29 kinaba: #include <iostream> 3d2bcff745 2011-12-29 kinaba: #include <sstream> 3d2bcff745 2011-12-29 kinaba: #include <iomanip> 3d2bcff745 2011-12-29 kinaba: #include <vector> 3d2bcff745 2011-12-29 kinaba: #include <string> 3d2bcff745 2011-12-29 kinaba: #include <map> 3d2bcff745 2011-12-29 kinaba: #include <set> 3d2bcff745 2011-12-29 kinaba: #include <algorithm> 3d2bcff745 2011-12-29 kinaba: #include <numeric> 3d2bcff745 2011-12-29 kinaba: #include <iterator> 3d2bcff745 2011-12-29 kinaba: #include <functional> 3d2bcff745 2011-12-29 kinaba: #include <complex> 3d2bcff745 2011-12-29 kinaba: #include <queue> 3d2bcff745 2011-12-29 kinaba: #include <stack> 3d2bcff745 2011-12-29 kinaba: #include <cmath> 3d2bcff745 2011-12-29 kinaba: #include <cassert> 3d2bcff745 2011-12-29 kinaba: #include <cstring> 3d2bcff745 2011-12-29 kinaba: #ifdef __GNUC__ 3d2bcff745 2011-12-29 kinaba: #include <ext/hash_map> 3d2bcff745 2011-12-29 kinaba: #define unordered_map __gnu_cxx::hash_map 3d2bcff745 2011-12-29 kinaba: #else 3d2bcff745 2011-12-29 kinaba: #include <unordered_map> 3d2bcff745 2011-12-29 kinaba: #endif 3d2bcff745 2011-12-29 kinaba: using namespace std; 3d2bcff745 2011-12-29 kinaba: typedef long long LL; 3d2bcff745 2011-12-29 kinaba: typedef complex<double> CMP; 3d2bcff745 2011-12-29 kinaba: 3d2bcff745 2011-12-29 kinaba: class Cut { public: 3d2bcff745 2011-12-29 kinaba: static bool TensFirst(int a, int b) 3d2bcff745 2011-12-29 kinaba: { 3d2bcff745 2011-12-29 kinaba: if(a%10 != b%10) 3d2bcff745 2011-12-29 kinaba: return a%10 < b%10; 3d2bcff745 2011-12-29 kinaba: return a < b; 3d2bcff745 2011-12-29 kinaba: } 3d2bcff745 2011-12-29 kinaba: 3d2bcff745 2011-12-29 kinaba: int getMaximum(vector <int> eelLengths, int maxCuts) 3d2bcff745 2011-12-29 kinaba: { 3d2bcff745 2011-12-29 kinaba: sort(eelLengths.begin(), eelLengths.end(), &TensFirst); 3d2bcff745 2011-12-29 kinaba: 3d2bcff745 2011-12-29 kinaba: int una = 0; 3d2bcff745 2011-12-29 kinaba: for(int i=0; i<eelLengths.size(); ++i) { 3d2bcff745 2011-12-29 kinaba: int e = eelLengths[i]; 3d2bcff745 2011-12-29 kinaba: while( maxCuts && e>10 ) 3d2bcff745 2011-12-29 kinaba: una++, maxCuts--, e-=10; 3d2bcff745 2011-12-29 kinaba: if( e == 10 ) 3d2bcff745 2011-12-29 kinaba: una++; 3d2bcff745 2011-12-29 kinaba: } 3d2bcff745 2011-12-29 kinaba: return una; 3d2bcff745 2011-12-29 kinaba: } 3d2bcff745 2011-12-29 kinaba: }; 3d2bcff745 2011-12-29 kinaba: 3d2bcff745 2011-12-29 kinaba: // BEGIN CUT HERE 3d2bcff745 2011-12-29 kinaba: #include <ctime> 3d2bcff745 2011-12-29 kinaba: double start_time; string timer() 3d2bcff745 2011-12-29 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 3d2bcff745 2011-12-29 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 3d2bcff745 2011-12-29 kinaba: { os << "{ "; 3d2bcff745 2011-12-29 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 3d2bcff745 2011-12-29 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 3d2bcff745 2011-12-29 kinaba: void verify_case(const int& Expected, const int& Received) { 3d2bcff745 2011-12-29 kinaba: bool ok = (Expected == Received); 3d2bcff745 2011-12-29 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 3d2bcff745 2011-12-29 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 3d2bcff745 2011-12-29 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 3d2bcff745 2011-12-29 kinaba: #define END verify_case(_, Cut().getMaximum(eelLengths, maxCuts));} 3d2bcff745 2011-12-29 kinaba: int main(){ 3d2bcff745 2011-12-29 kinaba: 3d2bcff745 2011-12-29 kinaba: CASE(0) 3d2bcff745 2011-12-29 kinaba: int eelLengths_[] = {13, 20, 13}; 3d2bcff745 2011-12-29 kinaba: vector <int> eelLengths(eelLengths_, eelLengths_+sizeof(eelLengths_)/sizeof(*eelLengths_)); 3d2bcff745 2011-12-29 kinaba: int maxCuts = 2; 3d2bcff745 2011-12-29 kinaba: int _ = 3; 3d2bcff745 2011-12-29 kinaba: END 3d2bcff745 2011-12-29 kinaba: CASE(1) 3d2bcff745 2011-12-29 kinaba: int eelLengths_[] = {5, 5, 5, 5}; 3d2bcff745 2011-12-29 kinaba: vector <int> eelLengths(eelLengths_, eelLengths_+sizeof(eelLengths_)/sizeof(*eelLengths_)); 3d2bcff745 2011-12-29 kinaba: int maxCuts = 2; 3d2bcff745 2011-12-29 kinaba: int _ = 0; 3d2bcff745 2011-12-29 kinaba: END 3d2bcff745 2011-12-29 kinaba: CASE(2) 3d2bcff745 2011-12-29 kinaba: int eelLengths_[] = {34, 10, 48}; 3d2bcff745 2011-12-29 kinaba: vector <int> eelLengths(eelLengths_, eelLengths_+sizeof(eelLengths_)/sizeof(*eelLengths_)); 3d2bcff745 2011-12-29 kinaba: int maxCuts = 4; 3d2bcff745 2011-12-29 kinaba: int _ = 5; 3d2bcff745 2011-12-29 kinaba: END 3d2bcff745 2011-12-29 kinaba: CASE(3) 3d2bcff745 2011-12-29 kinaba: int eelLengths_[] = {30, 50, 30, 50}; 3d2bcff745 2011-12-29 kinaba: vector <int> eelLengths(eelLengths_, eelLengths_+sizeof(eelLengths_)/sizeof(*eelLengths_)); 3d2bcff745 2011-12-29 kinaba: int maxCuts = 350; 3d2bcff745 2011-12-29 kinaba: int _ = 16; 3d2bcff745 2011-12-29 kinaba: END 3d2bcff745 2011-12-29 kinaba: /* 3d2bcff745 2011-12-29 kinaba: CASE(4) 3d2bcff745 2011-12-29 kinaba: int eelLengths_[] = ; 3d2bcff745 2011-12-29 kinaba: vector <int> eelLengths(eelLengths_, eelLengths_+sizeof(eelLengths_)/sizeof(*eelLengths_)); 3d2bcff745 2011-12-29 kinaba: int maxCuts = ; 3d2bcff745 2011-12-29 kinaba: int _ = ; 3d2bcff745 2011-12-29 kinaba: END 3d2bcff745 2011-12-29 kinaba: CASE(5) 3d2bcff745 2011-12-29 kinaba: int eelLengths_[] = ; 3d2bcff745 2011-12-29 kinaba: vector <int> eelLengths(eelLengths_, eelLengths_+sizeof(eelLengths_)/sizeof(*eelLengths_)); 3d2bcff745 2011-12-29 kinaba: int maxCuts = ; 3d2bcff745 2011-12-29 kinaba: int _ = ; 3d2bcff745 2011-12-29 kinaba: END 3d2bcff745 2011-12-29 kinaba: */ 3d2bcff745 2011-12-29 kinaba: } 3d2bcff745 2011-12-29 kinaba: // END CUT HERE