fc5b59158c 2014-03-04        kinaba: #include <iostream>
fc5b59158c 2014-03-04        kinaba: #include <sstream>
fc5b59158c 2014-03-04        kinaba: #include <iomanip>
fc5b59158c 2014-03-04        kinaba: #include <vector>
fc5b59158c 2014-03-04        kinaba: #include <string>
fc5b59158c 2014-03-04        kinaba: #include <map>
fc5b59158c 2014-03-04        kinaba: #include <set>
fc5b59158c 2014-03-04        kinaba: #include <algorithm>
fc5b59158c 2014-03-04        kinaba: #include <numeric>
fc5b59158c 2014-03-04        kinaba: #include <iterator>
fc5b59158c 2014-03-04        kinaba: #include <functional>
fc5b59158c 2014-03-04        kinaba: #include <complex>
fc5b59158c 2014-03-04        kinaba: #include <queue>
fc5b59158c 2014-03-04        kinaba: #include <stack>
fc5b59158c 2014-03-04        kinaba: #include <cmath>
fc5b59158c 2014-03-04        kinaba: #include <cassert>
fc5b59158c 2014-03-04        kinaba: #include <tuple>
fc5b59158c 2014-03-04        kinaba: using namespace std;
fc5b59158c 2014-03-04        kinaba: typedef long long LL;
fc5b59158c 2014-03-04        kinaba: typedef complex<double> CMP;
fc5b59158c 2014-03-04        kinaba: 
fc5b59158c 2014-03-04        kinaba: class TheMatrix { public:
fc5b59158c 2014-03-04        kinaba: 	int MaxArea(vector <string> board)
fc5b59158c 2014-03-04        kinaba: 	{
fc5b59158c 2014-03-04        kinaba: 		const int H = board.size(), W = board[0].size();
fc5b59158c 2014-03-04        kinaba: 		vector<vector<int>> yL(H, vector<int>(W));
fc5b59158c 2014-03-04        kinaba: 
fc5b59158c 2014-03-04        kinaba: 		for(int y=0; y<H; ++y)
fc5b59158c 2014-03-04        kinaba: 		for(int x=0; x<W; ++x)
fc5b59158c 2014-03-04        kinaba: 			for(yL[y][x]=1; y+yL[y][x]<H; ++yL[y][x])
fc5b59158c 2014-03-04        kinaba: 				if(board[y+yL[y][x]][x] == board[y+yL[y][x]-1][x])
fc5b59158c 2014-03-04        kinaba: 					break;
fc5b59158c 2014-03-04        kinaba: 
fc5b59158c 2014-03-04        kinaba: 		int best = 0;
fc5b59158c 2014-03-04        kinaba: 		for(int y=0; y<H; ++y)
fc5b59158c 2014-03-04        kinaba: 		for(int x=0; x<W; ++x)
fc5b59158c 2014-03-04        kinaba: 		{
fc5b59158c 2014-03-04        kinaba: 			int h = yL[y][x];
fc5b59158c 2014-03-04        kinaba: 			best = max(best, h*1);
fc5b59158c 2014-03-04        kinaba: 			for(int xd=1; x+xd<W; ++xd) if(board[y][x+xd] == board[y][x+xd-1]) break; else {
fc5b59158c 2014-03-04        kinaba: 				h = min(h, yL[y][x+xd]);
fc5b59158c 2014-03-04        kinaba: 				best = max(best, h*(xd+1));
fc5b59158c 2014-03-04        kinaba: 			}
fc5b59158c 2014-03-04        kinaba: 		}
fc5b59158c 2014-03-04        kinaba: 		return best;
fc5b59158c 2014-03-04        kinaba: 	}
fc5b59158c 2014-03-04        kinaba: };
fc5b59158c 2014-03-04        kinaba: 
fc5b59158c 2014-03-04        kinaba: // BEGIN CUT HERE
fc5b59158c 2014-03-04        kinaba: #include <ctime>
fc5b59158c 2014-03-04        kinaba: double start_time; string timer()
fc5b59158c 2014-03-04        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
fc5b59158c 2014-03-04        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
fc5b59158c 2014-03-04        kinaba:  { os << "{ ";
fc5b59158c 2014-03-04        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
fc5b59158c 2014-03-04        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
fc5b59158c 2014-03-04        kinaba: void verify_case(const int& Expected, const int& Received) {
fc5b59158c 2014-03-04        kinaba:  bool ok = (Expected == Received);
fc5b59158c 2014-03-04        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
fc5b59158c 2014-03-04        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
fc5b59158c 2014-03-04        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
fc5b59158c 2014-03-04        kinaba: #define END	 verify_case(_, TheMatrix().MaxArea(board));}
fc5b59158c 2014-03-04        kinaba: int main(){
fc5b59158c 2014-03-04        kinaba: CASE(0)
fc5b59158c 2014-03-04        kinaba: 	string board_[] = {"1",
fc5b59158c 2014-03-04        kinaba:  "0"};
fc5b59158c 2014-03-04        kinaba: 	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
fc5b59158c 2014-03-04        kinaba: 	int _ = 2;
fc5b59158c 2014-03-04        kinaba: END
fc5b59158c 2014-03-04        kinaba: CASE(1)
fc5b59158c 2014-03-04        kinaba: 	string board_[] = {"0000"};
fc5b59158c 2014-03-04        kinaba: 	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
fc5b59158c 2014-03-04        kinaba: 	int _ = 1;
fc5b59158c 2014-03-04        kinaba: END
fc5b59158c 2014-03-04        kinaba: CASE(2)
fc5b59158c 2014-03-04        kinaba: 	string board_[] = {"01"};
fc5b59158c 2014-03-04        kinaba: 	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
fc5b59158c 2014-03-04        kinaba: 	int _ = 2;
fc5b59158c 2014-03-04        kinaba: END
fc5b59158c 2014-03-04        kinaba: CASE(3)
fc5b59158c 2014-03-04        kinaba: 	string board_[] = {"001",
fc5b59158c 2014-03-04        kinaba:  "000",
fc5b59158c 2014-03-04        kinaba:  "100"};
fc5b59158c 2014-03-04        kinaba: 	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
fc5b59158c 2014-03-04        kinaba: 	int _ = 2;
fc5b59158c 2014-03-04        kinaba: END
fc5b59158c 2014-03-04        kinaba: CASE(4)
fc5b59158c 2014-03-04        kinaba: 	string board_[] = {"0"};
fc5b59158c 2014-03-04        kinaba: 	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
fc5b59158c 2014-03-04        kinaba: 	int _ = 1;
fc5b59158c 2014-03-04        kinaba: END
fc5b59158c 2014-03-04        kinaba: CASE(5)
fc5b59158c 2014-03-04        kinaba: 	string board_[] = {"101",
fc5b59158c 2014-03-04        kinaba:  "010"};
fc5b59158c 2014-03-04        kinaba: 	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
fc5b59158c 2014-03-04        kinaba: 	int _ = 6;
fc5b59158c 2014-03-04        kinaba: END
fc5b59158c 2014-03-04        kinaba: CASE(6)
fc5b59158c 2014-03-04        kinaba: 	string board_[] = {"101",
fc5b59158c 2014-03-04        kinaba:  "011",
fc5b59158c 2014-03-04        kinaba:  "101",
fc5b59158c 2014-03-04        kinaba:  "010"};
fc5b59158c 2014-03-04        kinaba: 	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
fc5b59158c 2014-03-04        kinaba: 	int _ = 8;
fc5b59158c 2014-03-04        kinaba: END
fc5b59158c 2014-03-04        kinaba: CASE(7)
fc5b59158c 2014-03-04        kinaba: 	string board_[] = {"11001110011000110001111001001110110011010110001011",
fc5b59158c 2014-03-04        kinaba:  "10100100010111111011111001011110101111010011100001",
fc5b59158c 2014-03-04        kinaba:  "11101111001110100110010101101100011100101000010001",
fc5b59158c 2014-03-04        kinaba:  "01000010001010101100010011111000100100110111111000",
fc5b59158c 2014-03-04        kinaba:  "10110100000101100000111000100001011101111101010010",
fc5b59158c 2014-03-04        kinaba:  "00111010000011100001110110010011010110010011100100",
fc5b59158c 2014-03-04        kinaba:  "01100001111101001101001101100001111000111001101010",
fc5b59158c 2014-03-04        kinaba:  "11010000000011011010100010000000111011001001100101",
fc5b59158c 2014-03-04        kinaba:  "10100000000100010100100011010100110110110001000001",
fc5b59158c 2014-03-04        kinaba:  "01101010101100001100000110100110100000010100100010",
fc5b59158c 2014-03-04        kinaba:  "11010000001110111111011010011110001101100011100010",
fc5b59158c 2014-03-04        kinaba:  "11101111000000011010011100100001100011111111110111",
fc5b59158c 2014-03-04        kinaba:  "11000001101100100011000110111010011001010100000001",
fc5b59158c 2014-03-04        kinaba:  "00100001111001010000101101100010000001100100001000",
fc5b59158c 2014-03-04        kinaba:  "01001110110111101011010000111111101011000110010111",
fc5b59158c 2014-03-04        kinaba:  "01001010000111111001100000100010101100100101010100",
fc5b59158c 2014-03-04        kinaba:  "11111101001101110011011011011000111001101100011011",
fc5b59158c 2014-03-04        kinaba:  "10000100110111000001110110010000000000111100101101",
fc5b59158c 2014-03-04        kinaba:  "01010011101101101110000011000110011111001111011100",
fc5b59158c 2014-03-04        kinaba:  "01101010011111010000011001111101011010011100001101",
fc5b59158c 2014-03-04        kinaba:  "11011000011000110010101111100000101011011111101100",
fc5b59158c 2014-03-04        kinaba:  "11100001001000110010100011001010101101001010001100",
fc5b59158c 2014-03-04        kinaba:  "11011011001100111101001100111100000101011101101011",
fc5b59158c 2014-03-04        kinaba:  "11110111100100101011100101111101000111001111110111",
fc5b59158c 2014-03-04        kinaba:  "00011001100110111100111100001100101001111100001111",
fc5b59158c 2014-03-04        kinaba:  "10001111100101110111001111100000000011110000100111",
fc5b59158c 2014-03-04        kinaba:  "10101010110110100110010001001010000111100110100011",
fc5b59158c 2014-03-04        kinaba:  "01100110100000001110101001101011001010001101110101",
fc5b59158c 2014-03-04        kinaba:  "10110101110100110110101001100111110000101111100110",
fc5b59158c 2014-03-04        kinaba:  "01011000001001101110100001101001110011001001110001",
fc5b59158c 2014-03-04        kinaba:  "00100101010001100110110101001010010100001011000011",
fc5b59158c 2014-03-04        kinaba:  "00011101100100001010100000000011000010100110011100",
fc5b59158c 2014-03-04        kinaba:  "11001001011000000101111111000000110010001101101110",
fc5b59158c 2014-03-04        kinaba:  "10101010110110010000010011001100110101110100111011",
fc5b59158c 2014-03-04        kinaba:  "01101001010111010001101000100011101001110101000110",
fc5b59158c 2014-03-04        kinaba:  "00110101101110110001110101110010100100110000101101",
fc5b59158c 2014-03-04        kinaba:  "11010101000111010011110011000001101111010011110011",
fc5b59158c 2014-03-04        kinaba:  "10010000010001110011011101001110110010001100011100",
fc5b59158c 2014-03-04        kinaba:  "00111101110001001100101001110100110010100110110000",
fc5b59158c 2014-03-04        kinaba:  "00010011011000101000100001101110111100100000010100",
fc5b59158c 2014-03-04        kinaba:  "01101110001101000001001000001011101010011101011110",
fc5b59158c 2014-03-04        kinaba:  "00000100110011001011101011110011011101100001110111",
fc5b59158c 2014-03-04        kinaba:  "00110011110000011001011100001110101010100110010110",
fc5b59158c 2014-03-04        kinaba:  "00111001010011011111010100000100100000101101110001",
fc5b59158c 2014-03-04        kinaba:  "10101101101110111110000011111011001011100011110001",
fc5b59158c 2014-03-04        kinaba:  "00101110010101111000001010110100001110111011100011",
fc5b59158c 2014-03-04        kinaba:  "01111110010100111010110001111000111101110100111011"};
fc5b59158c 2014-03-04        kinaba: 	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
fc5b59158c 2014-03-04        kinaba: 	int _ = 12;
fc5b59158c 2014-03-04        kinaba: END
fc5b59158c 2014-03-04        kinaba: /*
fc5b59158c 2014-03-04        kinaba: CASE(8)
fc5b59158c 2014-03-04        kinaba: 	string board_[] = ;
fc5b59158c 2014-03-04        kinaba: 	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
fc5b59158c 2014-03-04        kinaba: 	int _ = ;
fc5b59158c 2014-03-04        kinaba: END
fc5b59158c 2014-03-04        kinaba: CASE(9)
fc5b59158c 2014-03-04        kinaba: 	string board_[] = ;
fc5b59158c 2014-03-04        kinaba: 	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
fc5b59158c 2014-03-04        kinaba: 	int _ = ;
fc5b59158c 2014-03-04        kinaba: END
fc5b59158c 2014-03-04        kinaba: */
fc5b59158c 2014-03-04        kinaba: }
fc5b59158c 2014-03-04        kinaba: // END CUT HERE