解いた問題

11/02/2012

SRM559 Div1 Easy

250



class HyperKnight {
public:
  long long countCells(int a, int b, int numRows, int numColumns, int k)
  {
    const int H = numRows;
    const int W = numColumns;

    const int N = 6;

    int h[N] = {0, a, b, H - a, H - b, H};
    int w[N] = {0, a, b, W - a, W - b, W};

    sort(h, h + N);
    sort(w, w + N);

    const int D = 8;
    const int dh[D] = {+a, +a, -a, -a, +b, +b, -b, -b};
    const int dw[D] = {+b, -b, +b, -b, +a, -a, +a, -a};

    lli sum = 0;

    for (int i = 0; i + 1 < N; ++i) {
      for (int j = 0; j + 1 < N; ++j) {
        int cnt = 0;
        for (int d = 0; d < D; ++d) {
          int nh = h[i] + dh[d];
          int nw = w[j] + dw[d];
          if (nh < 0 || H <= nh) continue;
          if (nw < 0 || W <= nw) continue;
          ++cnt;
        }
        if (cnt == k) {
          sum += (lli)(h[i + 1] - h[i]) * (lli)(w[j + 1] - w[j]);
        }
      }
    }

    return sum;
  }
};