第2回 ドワンゴからの挑戦状 予選 D: 庭園
解法
ある高さ 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; }