• 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
                                                                                        >    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]] -
                                                                                        >    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)
                                                                                        >    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 
                                                                                        >    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()
                                                                                        >    64   cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' 
                                                                                        >    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_)/si
                                                                                        >    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_)/si
                                                                                        >    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_)/si
                                                                                        >    97          int _ = 0;
                                                                                        >    98  END
                                                                                        >    99  /*
                                                                                        >   100  CASE(3)
                                                                                        >   101          string chocolate_[] = ;
                                                                                        >   102            vector <string> chocolate(chocolate_, chocolate_+sizeof(chocolate_)/si
                                                                                        >   103          int _ = ;
                                                                                        >   104  END
                                                                                        >   105  CASE(4)
                                                                                        >   106          string chocolate_[] = ;
                                                                                        >   107            vector <string> chocolate(chocolate_, chocolate_+sizeof(chocolate_)/si
                                                                                        >   108          int _ = ;
                                                                                        >   109  END
                                                                                        >   110  */
                                                                                        >   111  }
                                                                                        >   112  // END CUT HERE

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

cannot compute difference between binary files