434b2a3462 2014-10-23        kinaba: #include <iostream>
434b2a3462 2014-10-23        kinaba: #include <sstream>
434b2a3462 2014-10-23        kinaba: #include <iomanip>
434b2a3462 2014-10-23        kinaba: #include <vector>
434b2a3462 2014-10-23        kinaba: #include <string>
434b2a3462 2014-10-23        kinaba: #include <map>
434b2a3462 2014-10-23        kinaba: #include <set>
434b2a3462 2014-10-23        kinaba: #include <algorithm>
434b2a3462 2014-10-23        kinaba: #include <numeric>
434b2a3462 2014-10-23        kinaba: #include <iterator>
434b2a3462 2014-10-23        kinaba: #include <functional>
434b2a3462 2014-10-23        kinaba: #include <complex>
434b2a3462 2014-10-23        kinaba: #include <queue>
434b2a3462 2014-10-23        kinaba: #include <stack>
434b2a3462 2014-10-23        kinaba: #include <cmath>
434b2a3462 2014-10-23        kinaba: #include <cassert>
434b2a3462 2014-10-23        kinaba: #include <tuple>
434b2a3462 2014-10-23        kinaba: using namespace std;
434b2a3462 2014-10-23        kinaba: typedef long long LL;
434b2a3462 2014-10-23        kinaba: typedef complex<double> CMP;
434b2a3462 2014-10-23        kinaba: 
434b2a3462 2014-10-23        kinaba: class ChocolateDividingEasy { public:
434b2a3462 2014-10-23        kinaba: 	int findBest(vector <string> chocolate)
434b2a3462 2014-10-23        kinaba: 	{
434b2a3462 2014-10-23        kinaba: 		const int H = chocolate.size();
434b2a3462 2014-10-23        kinaba: 		const int W = chocolate[0].size();
434b2a3462 2014-10-23        kinaba: 		vector<vector<int>> sum(H+1, vector<int>(W+1));
434b2a3462 2014-10-23        kinaba: 		for(int y=H-1; y>=0; --y)
434b2a3462 2014-10-23        kinaba: 		for(int x=W-1; x>=0; --x)
434b2a3462 2014-10-23        kinaba: 			sum[y][x] = (chocolate[y][x]-'0')+sum[y+1][x]+sum[y][x+1]-sum[y+1][x+1];
434b2a3462 2014-10-23        kinaba: 
434b2a3462 2014-10-23        kinaba: 		int best = 0;
434b2a3462 2014-10-23        kinaba: 		for(int y1=1; y1<H; ++y1)
434b2a3462 2014-10-23        kinaba: 		for(int y2=y1+1; y2<H; ++y2)
434b2a3462 2014-10-23        kinaba: 		for(int x1=1; x1<W; ++x1)
434b2a3462 2014-10-23        kinaba: 		for(int x2=x1+1; x2<W; ++x2)
434b2a3462 2014-10-23        kinaba: 		{
434b2a3462 2014-10-23        kinaba: 			int Y[] = {0, y1, y2, H};
434b2a3462 2014-10-23        kinaba: 			int X[] = {0, x1, x2, W};
434b2a3462 2014-10-23        kinaba: 			int smallest = 0x3fffffff;
434b2a3462 2014-10-23        kinaba: 			for(int i=0; i<3; ++i)
434b2a3462 2014-10-23        kinaba: 			for(int k=0; k<3; ++k)
434b2a3462 2014-10-23        kinaba: 			{
434b2a3462 2014-10-23        kinaba: 				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]];
434b2a3462 2014-10-23        kinaba: 				smallest = min(smallest, area);
434b2a3462 2014-10-23        kinaba: 			}
434b2a3462 2014-10-23        kinaba: 			best = max(best, smallest);
434b2a3462 2014-10-23        kinaba: 		}
434b2a3462 2014-10-23        kinaba: 		return best;
434b2a3462 2014-10-23        kinaba: 	}
434b2a3462 2014-10-23        kinaba: };
434b2a3462 2014-10-23        kinaba: 
434b2a3462 2014-10-23        kinaba: // BEGIN CUT HERE
434b2a3462 2014-10-23        kinaba: #include <ctime>
434b2a3462 2014-10-23        kinaba: double start_time; string timer()
434b2a3462 2014-10-23        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
434b2a3462 2014-10-23        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
434b2a3462 2014-10-23        kinaba:  { os << "{ ";
434b2a3462 2014-10-23        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
434b2a3462 2014-10-23        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
434b2a3462 2014-10-23        kinaba: void verify_case(const int& Expected, const int& Received) {
434b2a3462 2014-10-23        kinaba:  bool ok = (Expected == Received);
434b2a3462 2014-10-23        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
434b2a3462 2014-10-23        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
434b2a3462 2014-10-23        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
434b2a3462 2014-10-23        kinaba: #define END	 verify_case(_, ChocolateDividingEasy().findBest(chocolate));}
434b2a3462 2014-10-23        kinaba: int main(){
434b2a3462 2014-10-23        kinaba: 
434b2a3462 2014-10-23        kinaba: CASE(0)
434b2a3462 2014-10-23        kinaba: 	string chocolate_[] = {
434b2a3462 2014-10-23        kinaba: "9768",
434b2a3462 2014-10-23        kinaba: "6767",
434b2a3462 2014-10-23        kinaba: "5313"
434b2a3462 2014-10-23        kinaba: };
434b2a3462 2014-10-23        kinaba: 	  vector <string> chocolate(chocolate_, chocolate_+sizeof(chocolate_)/sizeof(*chocolate_));
434b2a3462 2014-10-23        kinaba: 	int _ = 3;
434b2a3462 2014-10-23        kinaba: END
434b2a3462 2014-10-23        kinaba: CASE(1)
434b2a3462 2014-10-23        kinaba: 	string chocolate_[] = {
434b2a3462 2014-10-23        kinaba: "36753562",
434b2a3462 2014-10-23        kinaba: "91270936",
434b2a3462 2014-10-23        kinaba: "06261879",
434b2a3462 2014-10-23        kinaba: "20237592",
434b2a3462 2014-10-23        kinaba: "28973612",
434b2a3462 2014-10-23        kinaba: "93194784"
434b2a3462 2014-10-23        kinaba: };
434b2a3462 2014-10-23        kinaba: 	  vector <string> chocolate(chocolate_, chocolate_+sizeof(chocolate_)/sizeof(*chocolate_));
434b2a3462 2014-10-23        kinaba: 	int _ = 15;
434b2a3462 2014-10-23        kinaba: END
434b2a3462 2014-10-23        kinaba: CASE(2)
434b2a3462 2014-10-23        kinaba: 	string chocolate_[] = {
434b2a3462 2014-10-23        kinaba: "012",
434b2a3462 2014-10-23        kinaba: "345",
434b2a3462 2014-10-23        kinaba: "678"
434b2a3462 2014-10-23        kinaba: };
434b2a3462 2014-10-23        kinaba: 	  vector <string> chocolate(chocolate_, chocolate_+sizeof(chocolate_)/sizeof(*chocolate_));
434b2a3462 2014-10-23        kinaba: 	int _ = 0;
434b2a3462 2014-10-23        kinaba: END
434b2a3462 2014-10-23        kinaba: /*
434b2a3462 2014-10-23        kinaba: CASE(3)
434b2a3462 2014-10-23        kinaba: 	string chocolate_[] = ;
434b2a3462 2014-10-23        kinaba: 	  vector <string> chocolate(chocolate_, chocolate_+sizeof(chocolate_)/sizeof(*chocolate_));
434b2a3462 2014-10-23        kinaba: 	int _ = ;
434b2a3462 2014-10-23        kinaba: END
434b2a3462 2014-10-23        kinaba: CASE(4)
434b2a3462 2014-10-23        kinaba: 	string chocolate_[] = ;
434b2a3462 2014-10-23        kinaba: 	  vector <string> chocolate(chocolate_, chocolate_+sizeof(chocolate_)/sizeof(*chocolate_));
434b2a3462 2014-10-23        kinaba: 	int _ = ;
434b2a3462 2014-10-23        kinaba: END
434b2a3462 2014-10-23        kinaba: */
434b2a3462 2014-10-23        kinaba: }
434b2a3462 2014-10-23        kinaba: // END CUT HERE