SRM623 Div1Easy UniformBoard

問題概要
'P'のみで作られる長方形区間の面積の最大値を求めよ。ただし、K回まで 'A' または 'P' を取って '.'(空) に置く操作ができる。

解法
1. 全ての 'A', 'P', '.' の数を数える。
2. 全ての長方形Rを全探索する。
3-1. '.' が全体の正方形のグリッドに一つも存在しないとき
　Rの中の 'A' の数がRの面積に一致するなら最大値を更新。
3-2. '.' が全体の正方形のグリッドに一つでも存在するなら
　「(Rの面積 - R内の林檎の数) が R外にある」かつ「R内の 'P' の数 * 2(退ける操作と 'A' を持ってくる操作) + R内の '.' の数 <= K」 ならば、最大値を更新する。

#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
class UniformBoard {
public:
  void summation(const vector<string> &board, int sum[][21], int N, char ch) {
    rep(i, N) rep(j, N) {
      sum[i+1][j+1] = sum[i+1][j] + sum[i][j+1] - sum[i][j] + (board[i][j] == ch);
    }
  }
  
  int getSum(int sum[][21], int i, int j, int k, int l) {
    return sum[k][l] - sum[i][l] - sum[k][j] + sum[i][j];
  }
  
  int getBoard(vector <string> board, int K) {
    const int N = board.size();
    int cntAllA = 0, cntAllP = 0, cntAllE;
    rep(i, N) rep(j, N) {
      cntAllA += board[i][j] == 'A';
      cntAllP += board[i][j] == 'P';
    }
    cntAllE = N*N-cntAllA-cntAllP;

    int sumA[21][21] = {}; summation(board, sumA, N, 'A');
    int sumP[21][21] = {}; summation(board, sumP, N, 'P');
    int sumE[21][21] = {}; summation(board, sumE, N, '.');
    
    int ans = 0;
    
    if(cntAllE == 0) {
      rep(i, N) rep(j, N) {
        REP(k, i+1, N+1) REP(l, j+1, N+1) {
          int numA = getSum(sumA, i, j, k, l);
          int area = (k-i)*(l-j);
          if(numA == area) ans = max(ans, area);
        }
      }
      return ans;
    }
    
    rep(i, N) rep(j, N) {
      REP(k, i+1, N+1) REP(l, j+1, N+1) {
        int numP = getSum(sumP, i, j, k, l);
        int numE = getSum(sumE, i, j, k, l);
        int area = (k-i)*(l-j);
        
        if(area > cntAllA) continue;
        if(numP*2 + numE > K) continue;
        ans = max(ans, area);
      }
    }
    
    return ans;
  }
};