• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

Added SRM/636-U/1A.cpp version [8bc8dad70f532eb2]

            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 <tuple>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +class ChocolateDividingEasy { public:
           23  + int findBest(vector <string> chocolate)
           24  + {
           25  +  const int H = chocolate.size();
           26  +  const int W = chocolate[0].size();
           27  +  vector<vector<int>> sum(H+1, vector<int>(W+1));
           28  +  for(int y=H-1; y>=0; --y)
           29  +  for(int x=W-1; x>=0; --x)
           30  +   sum[y][x] = (chocolate[y][x]-'0')+sum[y+1][x]+sum[y][x+1]-sum[y+1][x+1];
           31  +
           32  +  int best = 0;
           33  +  for(int y1=1; y1<H; ++y1)
           34  +  for(int y2=y1+1; y2<H; ++y2)
           35  +  for(int x1=1; x1<W; ++x1)
           36  +  for(int x2=x1+1; x2<W; ++x2)
           37  +  {
           38  +   int Y[] = {0, y1, y2, H};
           39  +   int X[] = {0, x1, x2, W};
           40  +   int smallest = 0x3fffffff;
           41  +   for(int i=0; i<3; ++i)
           42  +   for(int k=0; k<3; ++k)
           43  +   {
           44  +    int area = sum[Y[i]][X[k]] - sum[Y[i+1]][X[k]] - sum[Y[i]][X[k+1]] + sum[Y[i+1]][X[k+1]];
           45  +    smallest = min(smallest, area);
           46  +   }
           47  +   best = max(best, smallest);
           48  +  }
           49  +  return best;
           50  + }
           51  +};
           52  +
           53  +// BEGIN CUT HERE
           54  +#include <ctime>
           55  +double start_time; string timer()
           56  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           57  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           58  + { os << "{ ";
           59  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           60  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           61  +void verify_case(const int& Expected, const int& Received) {
           62  + bool ok = (Expected == Received);
           63  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           64  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           65  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           66  +#define END  verify_case(_, ChocolateDividingEasy().findBest(chocolate));}
           67  +int main(){
           68  +
           69  +CASE(0)
           70  + string chocolate_[] = {
           71  +"9768",
           72  +"6767",
           73  +"5313"
           74  +};
           75  +   vector <string> chocolate(chocolate_, chocolate_+sizeof(chocolate_)/sizeof(*chocolate_));
           76  + int _ = 3;
           77  +END
           78  +CASE(1)
           79  + string chocolate_[] = {
           80  +"36753562",
           81  +"91270936",
           82  +"06261879",
           83  +"20237592",
           84  +"28973612",
           85  +"93194784"
           86  +};
           87  +   vector <string> chocolate(chocolate_, chocolate_+sizeof(chocolate_)/sizeof(*chocolate_));
           88  + int _ = 15;
           89  +END
           90  +CASE(2)
           91  + string chocolate_[] = {
           92  +"012",
           93  +"345",
           94  +"678"
           95  +};
           96  +   vector <string> chocolate(chocolate_, chocolate_+sizeof(chocolate_)/sizeof(*chocolate_));
           97  + int _ = 0;
           98  +END
           99  +/*
          100  +CASE(3)
          101  + string chocolate_[] = ;
          102  +   vector <string> chocolate(chocolate_, chocolate_+sizeof(chocolate_)/sizeof(*chocolate_));
          103  + int _ = ;
          104  +END
          105  +CASE(4)
          106  + string chocolate_[] = ;
          107  +   vector <string> chocolate(chocolate_, chocolate_+sizeof(chocolate_)/sizeof(*chocolate_));
          108  + int _ = ;
          109  +END
          110  +*/
          111  +}
          112  +// END CUT HERE

Added SRM/636-U/1C.cpp version [dc2c2e96205c04d2]

cannot compute difference between binary files