ea99443fa2 2014-06-07 kinaba: #include <iostream> ea99443fa2 2014-06-07 kinaba: #include <sstream> ea99443fa2 2014-06-07 kinaba: #include <iomanip> ea99443fa2 2014-06-07 kinaba: #include <vector> ea99443fa2 2014-06-07 kinaba: #include <string> ea99443fa2 2014-06-07 kinaba: #include <map> ea99443fa2 2014-06-07 kinaba: #include <set> ea99443fa2 2014-06-07 kinaba: #include <algorithm> ea99443fa2 2014-06-07 kinaba: #include <numeric> ea99443fa2 2014-06-07 kinaba: #include <iterator> ea99443fa2 2014-06-07 kinaba: #include <functional> ea99443fa2 2014-06-07 kinaba: #include <complex> ea99443fa2 2014-06-07 kinaba: #include <queue> ea99443fa2 2014-06-07 kinaba: #include <stack> ea99443fa2 2014-06-07 kinaba: #include <cmath> ea99443fa2 2014-06-07 kinaba: #include <cassert> ea99443fa2 2014-06-07 kinaba: #include <tuple> ea99443fa2 2014-06-07 kinaba: using namespace std; ea99443fa2 2014-06-07 kinaba: typedef long long LL; ea99443fa2 2014-06-07 kinaba: typedef complex<double> CMP; ea99443fa2 2014-06-07 kinaba: ea99443fa2 2014-06-07 kinaba: class UniformBoard { public: ea99443fa2 2014-06-07 kinaba: int getBoard(vector <string> board, int K) ea99443fa2 2014-06-07 kinaba: { ea99443fa2 2014-06-07 kinaba: const int N = board.size(); ea99443fa2 2014-06-07 kinaba: ea99443fa2 2014-06-07 kinaba: int A=0, P=0; ea99443fa2 2014-06-07 kinaba: for(int y=0; y<N; ++y) ea99443fa2 2014-06-07 kinaba: for(int x=0; x<N; ++x) { ea99443fa2 2014-06-07 kinaba: if(board[y][x]=='P')++P; ea99443fa2 2014-06-07 kinaba: if(board[y][x]=='A')++A; ea99443fa2 2014-06-07 kinaba: } ea99443fa2 2014-06-07 kinaba: ea99443fa2 2014-06-07 kinaba: int best = 0; ea99443fa2 2014-06-07 kinaba: for(int y=0; y<N; ++y) ea99443fa2 2014-06-07 kinaba: for(int x=0; x<N; ++x) ea99443fa2 2014-06-07 kinaba: for(int yy=y+1; yy<=N; ++yy) ea99443fa2 2014-06-07 kinaba: for(int xx=x+1; xx<=N; ++xx) ea99443fa2 2014-06-07 kinaba: { ea99443fa2 2014-06-07 kinaba: int a=0, p=0; ea99443fa2 2014-06-07 kinaba: for(int i=y; i<yy; ++i) ea99443fa2 2014-06-07 kinaba: for(int k=x; k<xx; ++k) { ea99443fa2 2014-06-07 kinaba: if(board[i][k]=='P')++p; ea99443fa2 2014-06-07 kinaba: if(board[i][k]=='A')++a; ea99443fa2 2014-06-07 kinaba: } ea99443fa2 2014-06-07 kinaba: int move = calc(A,P,N*N-A-P,a,p,(yy-y)*(xx-x)-a-p); ea99443fa2 2014-06-07 kinaba: if(move<=K) ea99443fa2 2014-06-07 kinaba: best = max(best, (yy-y)*(xx-x)); ea99443fa2 2014-06-07 kinaba: } ea99443fa2 2014-06-07 kinaba: return best; ea99443fa2 2014-06-07 kinaba: } ea99443fa2 2014-06-07 kinaba: ea99443fa2 2014-06-07 kinaba: int calc(int A, int P, int E, int a, int p, int e) ea99443fa2 2014-06-07 kinaba: { ea99443fa2 2014-06-07 kinaba: const int INF = 0x7ffffff; ea99443fa2 2014-06-07 kinaba: A -= a; ea99443fa2 2014-06-07 kinaba: P -= p; ea99443fa2 2014-06-07 kinaba: E -= e; ea99443fa2 2014-06-07 kinaba: ea99443fa2 2014-06-07 kinaba: if(e+p > A) ea99443fa2 2014-06-07 kinaba: return INF; ea99443fa2 2014-06-07 kinaba: ea99443fa2 2014-06-07 kinaba: int move = 0; ea99443fa2 2014-06-07 kinaba: if(e) { ea99443fa2 2014-06-07 kinaba: move += e; ea99443fa2 2014-06-07 kinaba: E += e; ea99443fa2 2014-06-07 kinaba: A -= e; ea99443fa2 2014-06-07 kinaba: a += e; ea99443fa2 2014-06-07 kinaba: e = 0; ea99443fa2 2014-06-07 kinaba: } ea99443fa2 2014-06-07 kinaba: if(p) { ea99443fa2 2014-06-07 kinaba: if(E == 0) ea99443fa2 2014-06-07 kinaba: return INF; ea99443fa2 2014-06-07 kinaba: move += 2*p; ea99443fa2 2014-06-07 kinaba: } ea99443fa2 2014-06-07 kinaba: return move; ea99443fa2 2014-06-07 kinaba: } ea99443fa2 2014-06-07 kinaba: }; ea99443fa2 2014-06-07 kinaba: ea99443fa2 2014-06-07 kinaba: // BEGIN CUT HERE ea99443fa2 2014-06-07 kinaba: #include <ctime> ea99443fa2 2014-06-07 kinaba: double start_time; string timer() ea99443fa2 2014-06-07 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } ea99443fa2 2014-06-07 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) ea99443fa2 2014-06-07 kinaba: { os << "{ "; ea99443fa2 2014-06-07 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) ea99443fa2 2014-06-07 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } ea99443fa2 2014-06-07 kinaba: void verify_case(const int& Expected, const int& Received) { ea99443fa2 2014-06-07 kinaba: bool ok = (Expected == Received); ea99443fa2 2014-06-07 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; ea99443fa2 2014-06-07 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } ea99443fa2 2014-06-07 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); ea99443fa2 2014-06-07 kinaba: #define END verify_case(_, UniformBoard().getBoard(board, K));} ea99443fa2 2014-06-07 kinaba: int main(){ ea99443fa2 2014-06-07 kinaba: ea99443fa2 2014-06-07 kinaba: CASE(0) ea99443fa2 2014-06-07 kinaba: string board_[] = {"AP", ea99443fa2 2014-06-07 kinaba: ".A"}; ea99443fa2 2014-06-07 kinaba: vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); ea99443fa2 2014-06-07 kinaba: int K = 0; ea99443fa2 2014-06-07 kinaba: int _ = 1; ea99443fa2 2014-06-07 kinaba: END ea99443fa2 2014-06-07 kinaba: CASE(1) ea99443fa2 2014-06-07 kinaba: string board_[] = {"AP", ea99443fa2 2014-06-07 kinaba: ".A"}; ea99443fa2 2014-06-07 kinaba: vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); ea99443fa2 2014-06-07 kinaba: int K = 1; ea99443fa2 2014-06-07 kinaba: int _ = 2; ea99443fa2 2014-06-07 kinaba: END ea99443fa2 2014-06-07 kinaba: CASE(2) ea99443fa2 2014-06-07 kinaba: string board_[] = {"PPP", ea99443fa2 2014-06-07 kinaba: "APA", ea99443fa2 2014-06-07 kinaba: "A.P"}; ea99443fa2 2014-06-07 kinaba: vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); ea99443fa2 2014-06-07 kinaba: int K = 2; ea99443fa2 2014-06-07 kinaba: int _ = 3; ea99443fa2 2014-06-07 kinaba: END ea99443fa2 2014-06-07 kinaba: CASE(3) ea99443fa2 2014-06-07 kinaba: string board_[] = {"AAA", ea99443fa2 2014-06-07 kinaba: "PPP", ea99443fa2 2014-06-07 kinaba: "AAA"}; ea99443fa2 2014-06-07 kinaba: vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); ea99443fa2 2014-06-07 kinaba: int K = 10; ea99443fa2 2014-06-07 kinaba: int _ = 3; ea99443fa2 2014-06-07 kinaba: END ea99443fa2 2014-06-07 kinaba: CASE(4) ea99443fa2 2014-06-07 kinaba: string board_[] = {"."}; ea99443fa2 2014-06-07 kinaba: vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); ea99443fa2 2014-06-07 kinaba: int K = 1000; ea99443fa2 2014-06-07 kinaba: int _ = 0; ea99443fa2 2014-06-07 kinaba: END ea99443fa2 2014-06-07 kinaba: CASE(5) ea99443fa2 2014-06-07 kinaba: string board_[] = {"PPAAPA..AP", ea99443fa2 2014-06-07 kinaba: "PPA.APAP..", ea99443fa2 2014-06-07 kinaba: "..P.AA.PPP", ea99443fa2 2014-06-07 kinaba: "P.P..APAA.", ea99443fa2 2014-06-07 kinaba: "P.P..P.APA", ea99443fa2 2014-06-07 kinaba: "PPA..AP.AA", ea99443fa2 2014-06-07 kinaba: "APP..AAPAA", ea99443fa2 2014-06-07 kinaba: "P.P.AP...P", ea99443fa2 2014-06-07 kinaba: ".P.A.PAPPA", ea99443fa2 2014-06-07 kinaba: "..PAPAP..P"}; ea99443fa2 2014-06-07 kinaba: vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); ea99443fa2 2014-06-07 kinaba: int K = 10; ea99443fa2 2014-06-07 kinaba: int _ = 15; ea99443fa2 2014-06-07 kinaba: END ea99443fa2 2014-06-07 kinaba: /* ea99443fa2 2014-06-07 kinaba: CASE(6) ea99443fa2 2014-06-07 kinaba: string board_[] = ; ea99443fa2 2014-06-07 kinaba: vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); ea99443fa2 2014-06-07 kinaba: int K = ; ea99443fa2 2014-06-07 kinaba: int _ = ; ea99443fa2 2014-06-07 kinaba: END ea99443fa2 2014-06-07 kinaba: CASE(7) ea99443fa2 2014-06-07 kinaba: string board_[] = ; ea99443fa2 2014-06-07 kinaba: vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); ea99443fa2 2014-06-07 kinaba: int K = ; ea99443fa2 2014-06-07 kinaba: int _ = ; ea99443fa2 2014-06-07 kinaba: END ea99443fa2 2014-06-07 kinaba: */ ea99443fa2 2014-06-07 kinaba: } ea99443fa2 2014-06-07 kinaba: // END CUT HERE