Submission #67723912

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#include<atcoder/all>
using namespace atcoder;
using mint=atcoder::modint998244353;

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define rng(i,l,r) for(int i=(l);i<(r);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrng(i,l,r) for(int i=(r)-1;i>=l;i--)
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()

struct fast_io{fast_io(){cin.tie(nullptr)->sync_with_stdio(false);}}_;

signed main(){
    int H,W;cin>>H>>W;

    vector<vector<int>> A(H,vector<int>(W));
    rep(i,H)rep(j,W)cin>>A[i][j];

    vector<int> P(H+W-1);
    rep(i,H+W-1)cin>>P[i];

    auto judge=[&](int x)->bool {
        vector<vector<int>> dp(H,vector<int>(W,-1e18));
        dp[0][0]=A[0][0]+x;

        rep(i,H)rep(j,W){
            if(dp[i][j]<P[i+j])continue;
            if(i==H-1&&j==W-1)return 1;
            dp[i][j]-=P[i+j];
            if(i!=H-1)dp[i+1][j]=max(dp[i+1][j],dp[i][j]+A[i+1][j]);
            if(j!=W-1)dp[i][j+1]=max(dp[i][j+1],dp[i][j]+A[i][j+1]);
        }

        return 0;
    };

    int ok=1e15,ng=-1;
    while(abs(ok-ng)>1){
        int m=(ok+ng)>>1;
        if(judge(m))ok=m;
        else ng=m;
    }

    cout<<ok<<"\n";
}

Submission Info

Judge Result