提出 #67725061

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)1e18;

class Solution {
    int H, W;
    vector<vector<ll>> A;
    vector<ll> P, dp, ndp;

    bool check(ll x) {
        dp.assign(W+1, -INF);
        ndp.assign(W+1, -INF);
        dp[1] = x;
        for (int i = 1; i <= H; ++i) {
            fill(ndp.begin(), ndp.end(), -INF);
            for (int j = 1; j <= W; ++j) {
                ll prev = -INF;
                if (i == 1 && j == 1) prev = dp[1];
                else {
                    if (i > 1) prev = max(prev, dp[j]);
                    if (j > 1) prev = max(prev, ndp[j-1]);
                }
                if (prev < 0) continue;
                ll now = prev + A[i-1][j-1] - P[i+j-1];
                if (now >= 0) ndp[j] = now;
            }
            dp.swap(ndp);
        }
        return dp[W] >= 0;
    }

    ll binary() {
        ll lo = 0, hi = (ll)1e15;
        while (lo < hi) {
            ll mid = lo + (hi - lo) / 2;
            if (check(mid)) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }

public:
    void solve() {
        cin >> H >> W;
        A.assign(H, vector<ll>(W));
        for (int i = 0; i < H; ++i)
            for (int j = 0; j < W; ++j)
                cin >> A[i][j];
        P.assign(H+W, 0);
        for (int k = 1; k <= H+W-1; ++k)
            cin >> P[k];
        cout << binary() << "\n";
    }
};

int main(){
    Solution* s = new Solution();
    s->solve();
    return 0;
}

提出情報

ジャッジ結果