Overview
| SHA1 Hash: | 90dd89d9afe6f2456000ba3d2c33e8c93f7e2f85 |
|---|---|
| Date: | 2012-03-17 14:58:06 |
| User: | kinaba |
| Comment: | 536 |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
Added SRM/536-U/1A.cpp version [a01ad9bff4f4fef1]
> 1 #include <iostream> > 2 #include <sstream> > 3 #include <iomanip> > 4 #include <vector> > 5 #include <string> > 6 #include <map> > 7 #include <set> > 8 #include <algorithm> > 9 #include <numeric> > 10 #include <iterator> > 11 #include <functional> > 12 #include <complex> > 13 #include <queue> > 14 #include <stack> > 15 #include <cmath> > 16 #include <cassert> > 17 #include <cstring> > 18 #ifdef __GNUC__ > 19 #include <ext/hash_map> > 20 #define unordered_map __gnu_cxx::hash_map > 21 #else > 22 #include <unordered_map> > 23 #endif > 24 using namespace std; > 25 typedef long long LL; > 26 typedef complex<double> CMP; > 27 > 28 class MergersDivOne { public: > 29 double findMaximum(vector <int> revenues) > 30 { > 31 vector<double> r(revenues.begin(), revenues.end()); > 32 sort(r.begin(), r.end()); > 33 return best(r, r.size()); > 34 } > 35 > 36 > 37 map<int, double> memo; > 38 double best(const vector<double>& r, int N) > 39 { > 40 if( N == 1 ) > 41 return r[0]; > 42 if( memo.count(N) ) > 43 return memo[N]; > 44 > 45 double score = -1e+100; > 46 for(int k=1; k<N; ++k) { > 47 double a = accumulate(r.begin()+k, r.begin()+N, best(r, > 48 score = max(score, a); > 49 } > 50 return memo[N] = score; > 51 } > 52 }; > 53 > 54 // BEGIN CUT HERE > 55 #include <ctime> > 56 double start_time; string timer() > 57 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 58 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 59 { os << "{ "; > 60 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 61 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 62 void verify_case(const double& Expected, const double& Received) { > 63 bool ok = (abs(Expected - Received) < 1e-9); > 64 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 65 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 66 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 67 #define END verify_case(_, MergersDivOne().findMaximum(revenues));} > 68 int main(){ > 69 > 70 CASE(0) > 71 int revenues_[] = {5, -7, 3}; > 72 vector <int> revenues(revenues_, revenues_+sizeof(revenues_)/sizeof(*r > 73 double _ = 1.5; > 74 END > 75 CASE(1) > 76 int revenues_[] = {10, -17}; > 77 vector <int> revenues(revenues_, revenues_+sizeof(revenues_)/sizeof(*r > 78 double _ = -3.5; > 79 END > 80 CASE(2) > 81 int revenues_[] = {12, 12, 12, 12, 12}; > 82 vector <int> revenues(revenues_, revenues_+sizeof(revenues_)/sizeof(*r > 83 double _ = 12.0; > 84 END > 85 CASE(3) > 86 int revenues_[] = {0, 0, 0, 0, 0, 100}; > 87 vector <int> revenues(revenues_, revenues_+sizeof(revenues_)/sizeof(*r > 88 double _ = 50.0; > 89 END > 90 CASE(4) > 91 int revenues_[] = {10, -10, 100, -100, 1000, -1000}; > 92 vector <int> revenues(revenues_, revenues_+sizeof(revenues_)/sizeof(*r > 93 double _ = 491.25; > 94 END > 95 CASE(5) > 96 int revenues_[] = {0,0,100,100}; > 97 vector <int> revenues(revenues_, revenues_+sizeof(revenues_)/sizeof(*r > 98 double _ = -1; > 99 END > 100 /* > 101 CASE(6) > 102 int revenues_[] = ; > 103 vector <int> revenues(revenues_, revenues_+sizeof(revenues_)/sizeof(*r > 104 double _ = ; > 105 END > 106 */ > 107 } > 108 // END CUT HERE
Added SRM/536-U/1B-U.cpp version [0853e7c70823346d]
> 1 #include <iostream> > 2 #include <sstream> > 3 #include <iomanip> > 4 #include <vector> > 5 #include <string> > 6 #include <map> > 7 #include <set> > 8 #include <algorithm> > 9 #include <numeric> > 10 #include <iterator> > 11 #include <functional> > 12 #include <complex> > 13 #include <queue> > 14 #include <stack> > 15 #include <cmath> > 16 #include <cassert> > 17 #include <cstring> > 18 #ifdef __GNUC__ > 19 #include <ext/hash_map> > 20 #define unordered_map __gnu_cxx::hash_map > 21 #else > 22 #include <unordered_map> > 23 #endif > 24 using namespace std; > 25 typedef long long LL; > 26 typedef complex<double> CMP; > 27 > 28 class RollingDiceDivOne { public: > 29 long long mostLikely(vector <int> dice) > 30 { > 31 sort(dice.begin(), dice.end()); > 32 if( dice.size() == 1 ) > 33 return 1; > 34 > 35 > 36 LL m2sum = 0; > 37 for(int i=0; i<dice.size(); ++i) > 38 m2sum += dice[i]+1; > 39 LL v = m2sum / 2; > 40 return v; > 41 } > 42 }; > 43 > 44 // BEGIN CUT HERE > 45 #include <ctime> > 46 double start_time; string timer() > 47 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 48 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 49 { os << "{ "; > 50 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 51 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 52 void verify_case(const long long& Expected, const long long& Received) { > 53 bool ok = (Expected == Received); > 54 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 55 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 56 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 57 #define END verify_case(_, RollingDiceDivOne().mostLikely(dice));} > 58 int main(){ > 59 > 60 CASE(0) > 61 int dice_[] = {6, 6, 8}; > 62 vector <int> dice(dice_, dice_+sizeof(dice_)/sizeof(*dice_)); > 63 long long _ = 11LL; > 64 END > 65 CASE(1) > 66 int dice_[] = {10}; > 67 vector <int> dice(dice_, dice_+sizeof(dice_)/sizeof(*dice_)); > 68 long long _ = 1LL; > 69 END > 70 CASE(2) > 71 int dice_[] = {2, 3, 4, 5}; > 72 vector <int> dice(dice_, dice_+sizeof(dice_)/sizeof(*dice_)); > 73 long long _ = 9LL; > 74 END > 75 CASE(3) > 76 int dice_[] = {1, 10, 1}; > 77 vector <int> dice(dice_, dice_+sizeof(dice_)/sizeof(*dice_)); > 78 long long _ = 3LL; > 79 END > 80 CASE(4) > 81 int dice_[] = {382828264, 942663792, 291832707, 887961277, 546603677, 54 > 82 700781193, 452172304, 816532384, 951089120, 448136091, 280899512, 256093435, 395 > 83 vector <int> dice(dice_, dice_+sizeof(dice_)/sizeof(*dice_)); > 84 long long _ = 4366828428LL; > 85 END > 86 CASE(5) > 87 int dice_[] = {686070183,764446558,958676845,711114086,307405925,1834583 > 88 vector <int> dice(dice_, dice_+sizeof(dice_)/sizeof(*dice_)); > 89 long long _ = -1LL; > 90 END > 91 CASE(6) > 92 int dice_[] = {1}; > 93 vector <int> dice(dice_, dice_+sizeof(dice_)/sizeof(*dice_)); > 94 long long _ = 1LL; > 95 END > 96 > 97 } > 98 // END CUT HERE