Submission #2036279

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/






int H, W; ll P[10][50101], F[10][50101];
//---------------------------------------------------------------------------------------------------
vector<ll> update(vector<ll> &dp, ll *p, ll *f) {
    vector<ll> A(W), B(W), res(W);

    rep(x, 1, W) A[x] = max(p[x - 1] - f[x - 1], A[x - 1] + p[x - 1] - f[x - 1] * 2);
    rrep(x, W - 2, 0) B[x] = max(p[x + 1] - f[x + 1], B[x + 1] + p[x + 1] - f[x + 1] * 2);

    ll ma = -infl;
    rep(x, 0, W) {
        ma = max(max(ma + p[x] - f[x], dp[x] + A[x] + p[x] - f[x] * 2), dp[x] + p[x] - f[x]);
        res[x] = max(ma + B[x] - f[x], ma);
    }
    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) rep(x, 0, W) cin >> P[y][x];
    rep(y, 0, H) rep(x, 0, W) cin >> F[y][x];

    vector<ll> dp(W, -infl);
    dp[0] = 0;

    rep(y, 0, H) {
        auto pd1 = update(dp, P[y], F[y]);

        reverse(dp.begin(), dp.end());
        reverse(P[y], P[y] + W);
        reverse(F[y], F[y] + W);

        auto pd2 = update(dp, P[y], F[y]);

        rep(x, 0, W) dp[x] = max(pd1[x], pd2[W - 1 - x]);
    }

    rep(x, 0, W) printf("%lld\n", dp[x]);
}

Submission Info

Judge Result