読者です 読者をやめる 読者になる 読者になる

第2回 ドワンゴからの挑戦状 予選 D: 庭園

競技プログラミング AtCoder

解法

ある高さ h よりも上の部分でできる長方形の最大値と、下の部分でできる長方形の合計を最大化することを考え、hを全て試せば良い。

コード

#include <bits/stdc++.h>
using namespace std;

template <class T, class U>
void chmax(T &t, U f) {
  if (t < f) t = f;
}

template <class T>
class CumulativeSum {
  int ny, nx;
  vector<vector<T>> sum;

 public:
  CumulativeSum(const vector<vector<T>> &a) {
    ny = a.size();
    nx = a[0].size();
    sum.assign(ny + 1, vector<T>(nx + 1, 0));
    for (int i = 0; i < ny; ++i) {
      for (int j = 0; j < nx; ++j) {
        sum[i + 1][j + 1] = a[i][j] + sum[i][j + 1] + sum[i + 1][j] - sum[i][j];
      }
    }
  }

  T getSum(int y1, int x1, int y2, int x2) {
    if (y1 > y2 || x1 > x2) return 0;
    y1 = max(y1, 0);
    x1 = max(x1, 0);
    y2 = min(y2, ny - 1);
    x2 = min(x2, nx - 1);
    return sum[y2 + 1][x2 + 1] - sum[y1][x2 + 1] - sum[y2 + 1][x1] +
           sum[y1][x1];
  }
};

int64_t solve(const vector<vector<int64_t>> &garden) {
  CumulativeSum<int64_t> cumsum(garden);
  int H = garden.size();
  int W = garden[0].size();
  vector<int64_t> top(H + 1, -1e17), bottom(H + 1, -1e18);
  for (int h1 = 0; h1 < H; ++h1) {
    for (int h2 = h1; h2 < H; ++h2) {
      // Calculate maximum value in [h1, h2]
      int64_t ma = -1e17, dp = -1e17;
      for (int k = 0; k < W; ++k) {
        int64_t x = cumsum.getSum(h1, k, h2, k);
        dp = max(dp + x, x);
        chmax(ma, dp);
      }
      chmax(bottom[h1], ma);
      chmax(top[h2], ma);
    }
  }
  for (int i = 1; i <= H; ++i) chmax(top[i], top[i - 1]);
  for (int i = 0; i < H; ++i) chmax(bottom[i], bottom[i + 1]);

  int64_t ans = -1e17;
  for (int i = 0; i < H - 1; ++i) chmax(ans, top[i] + bottom[i + 1]);
  return ans;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int H, W;
  cin >> H >> W;
  vector<vector<int64_t>> garden(H, vector<int64_t>(W));
  for (int h = 0; h < H; ++h)
    for (int w = 0; w < W; ++w) cin >> garden[h][w];

  vector<vector<int64_t>> gardenT(W, vector<int64_t>(H));
  for (int h = 0; h < H; ++h)
    for (int w = 0; w < W; ++w) gardenT[w][h] = garden[h][w];

  int64_t ans1 = solve(garden);
  int64_t ans2 = solve(gardenT);
  cout << max(ans1, ans2) << endl;
}