SRM452 Div1 Easy

250
試しに石を置いて数える。計算もで出せるみたい。
小さい場合を手で描いてみると分かりやすい。

class NotTwo {
public:
  int maxStones(int W, int H) 
  { 

    int di[] = {0, 0, 1, 1};
    int dj[] = {0, 1, 0, 1};

    bool g[H][W];
    fill(&g[0][0], &g[H - 1][W], false);

    for (int i = 0; i < H; i += 2) {
      for (int j = 0; j < W; j += 2) {
        int k = (i / 2) + (j / 2);
        if (k % 2) continue;
        for (int d = 0; d < 4; ++d) {
          int ni = i + di[d];
          int nj = j + dj[d];
          if (ni < 0 || nj < 0) continue;
          if (H <= ni || W <= nj) continue;
          g[ni][nj] = true;
        }
      }
    }  

    return count(&g[0][0], &g[H - 1][W], true);
  }

};