ADDED SRM/536-U/1A.cpp
Index: SRM/536-U/1A.cpp
==================================================================
--- SRM/536-U/1A.cpp
+++ SRM/536-U/1A.cpp
@@ -0,0 +1,108 @@
+#include <iostream>
+#include <sstream>
+#include <iomanip>
+#include <vector>
+#include <string>
+#include <map>
+#include <set>
+#include <algorithm>
+#include <numeric>
+#include <iterator>
+#include <functional>
+#include <complex>
+#include <queue>
+#include <stack>
+#include <cmath>
+#include <cassert>
+#include <cstring>
+#ifdef __GNUC__
+#include <ext/hash_map>
+#define unordered_map __gnu_cxx::hash_map
+#else
+#include <unordered_map>
+#endif
+using namespace std;
+typedef long long LL;
+typedef complex<double> CMP;
+
+class MergersDivOne { public:
+ double findMaximum(vector <int> revenues)
+ {
+ vector<double> r(revenues.begin(), revenues.end());
+ sort(r.begin(), r.end());
+ return best(r, r.size());
+ }
+
+
+ map<int, double> memo;
+ double best(const vector<double>& r, int N)
+ {
+ if( N == 1 )
+ return r[0];
+ if( memo.count(N) )
+ return memo[N];
+
+ double score = -1e+100;
+ for(int k=1; k<N; ++k) {
+ double a = accumulate(r.begin()+k, r.begin()+N, best(r, k)) / (N-k+1);
+ score = max(score, a);
+ }
+ return memo[N] = score;
+ }
+};
+
+// BEGIN CUT HERE
+#include <ctime>
+double start_time; string timer()
+ { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
+template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
+ { os << "{ ";
+ for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
+ os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
+void verify_case(const double& Expected, const double& Received) {
+ bool ok = (abs(Expected - Received) < 1e-9);
+ if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
+ cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
+#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
+#define END verify_case(_, MergersDivOne().findMaximum(revenues));}
+int main(){
+
+CASE(0)
+ int revenues_[] = {5, -7, 3};
+ vector <int> revenues(revenues_, revenues_+sizeof(revenues_)/sizeof(*revenues_));
+ double _ = 1.5;
+END
+CASE(1)
+ int revenues_[] = {10, -17};
+ vector <int> revenues(revenues_, revenues_+sizeof(revenues_)/sizeof(*revenues_));
+ double _ = -3.5;
+END
+CASE(2)
+ int revenues_[] = {12, 12, 12, 12, 12};
+ vector <int> revenues(revenues_, revenues_+sizeof(revenues_)/sizeof(*revenues_));
+ double _ = 12.0;
+END
+CASE(3)
+ int revenues_[] = {0, 0, 0, 0, 0, 100};
+ vector <int> revenues(revenues_, revenues_+sizeof(revenues_)/sizeof(*revenues_));
+ double _ = 50.0;
+END
+CASE(4)
+ int revenues_[] = {10, -10, 100, -100, 1000, -1000};
+ vector <int> revenues(revenues_, revenues_+sizeof(revenues_)/sizeof(*revenues_));
+ double _ = 491.25;
+END
+CASE(5)
+int revenues_[] = {0,0,100,100};
+ vector <int> revenues(revenues_, revenues_+sizeof(revenues_)/sizeof(*revenues_));
+ double _ = -1;
+END
+/*
+CASE(6)
+ int revenues_[] = ;
+ vector <int> revenues(revenues_, revenues_+sizeof(revenues_)/sizeof(*revenues_));
+ double _ = ;
+END
+*/
+}
+// END CUT HERE
ADDED SRM/536-U/1B-U.cpp
Index: SRM/536-U/1B-U.cpp
==================================================================
--- SRM/536-U/1B-U.cpp
+++ SRM/536-U/1B-U.cpp
@@ -0,0 +1,98 @@
+#include <iostream>
+#include <sstream>
+#include <iomanip>
+#include <vector>
+#include <string>
+#include <map>
+#include <set>
+#include <algorithm>
+#include <numeric>
+#include <iterator>
+#include <functional>
+#include <complex>
+#include <queue>
+#include <stack>
+#include <cmath>
+#include <cassert>
+#include <cstring>
+#ifdef __GNUC__
+#include <ext/hash_map>
+#define unordered_map __gnu_cxx::hash_map
+#else
+#include <unordered_map>
+#endif
+using namespace std;
+typedef long long LL;
+typedef complex<double> CMP;
+
+class RollingDiceDivOne { public:
+ long long mostLikely(vector <int> dice)
+ {
+ sort(dice.begin(), dice.end());
+ if( dice.size() == 1 )
+ return 1;
+
+
+ LL m2sum = 0;
+ for(int i=0; i<dice.size(); ++i)
+ m2sum += dice[i]+1;
+ LL v = m2sum / 2;
+ return v;
+ }
+};
+
+// BEGIN CUT HERE
+#include <ctime>
+double start_time; string timer()
+ { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
+template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
+ { os << "{ ";
+ for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
+ os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
+void verify_case(const long long& Expected, const long long& Received) {
+ bool ok = (Expected == Received);
+ if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
+ cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
+#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
+#define END verify_case(_, RollingDiceDivOne().mostLikely(dice));}
+int main(){
+
+CASE(0)
+ int dice_[] = {6, 6, 8};
+ vector <int> dice(dice_, dice_+sizeof(dice_)/sizeof(*dice_));
+ long long _ = 11LL;
+END
+CASE(1)
+ int dice_[] = {10};
+ vector <int> dice(dice_, dice_+sizeof(dice_)/sizeof(*dice_));
+ long long _ = 1LL;
+END
+CASE(2)
+ int dice_[] = {2, 3, 4, 5};
+ vector <int> dice(dice_, dice_+sizeof(dice_)/sizeof(*dice_));
+ long long _ = 9LL;
+END
+CASE(3)
+ int dice_[] = {1, 10, 1};
+ vector <int> dice(dice_, dice_+sizeof(dice_)/sizeof(*dice_));
+ long long _ = 3LL;
+END
+CASE(4)
+ int dice_[] = {382828264, 942663792, 291832707, 887961277, 546603677, 545185615, 146267547, 6938117, 167567032, 84232402,
+700781193, 452172304, 816532384, 951089120, 448136091, 280899512, 256093435, 39595226, 631504901, 154772240};
+ vector <int> dice(dice_, dice_+sizeof(dice_)/sizeof(*dice_));
+ long long _ = 4366828428LL;
+END
+CASE(5)
+ int dice_[] = {686070183,764446558,958676845,711114086,307405925,18345836,534933273,884410953,402311475,699530578,734067293,586174895,653276411,461102667,361634525,515961596,53576037,909418211,678589501,398850606,279452824,544186770,203263120,85451598,330889574,93199510,730144410,620028986,247001511,285471536,706978584,976668932,10197700,550812603,440712526,127306784,280595874,519698127,482194343,519518638,680491824,236933627,69469348,993453692,817501995,678439028,166742435,200336684,724838900,525355524};
+ vector <int> dice(dice_, dice_+sizeof(dice_)/sizeof(*dice_));
+ long long _ = -1LL;
+END
+CASE(6)
+ int dice_[] = {1};
+ vector <int> dice(dice_, dice_+sizeof(dice_)/sizeof(*dice_));
+ long long _ = 1LL;
+END
+
+}
+// END CUT HERE