Submission #68171756

---

Source Code Expand

//#pragma GCC optimize("O3")
//#pragma GCC optimization("Ofast,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long int
#define endl '\n'
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ext exit(0)
#define INF 1000000000000000000
#define DIMBIT 32
#define fsort(a) sort(a.begin(), a.end())
#define fsortc(a, b) sort(a.begin(), a.end(), b)
#define pb push_back
#define frev(a) reverse(a.begin(), a.end())
#define fr first
#define se second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef pair<ll, ll> llpair;
#define ull unsigned long long
typedef pair<ll, ull> upair;
#define sz(a) int(a.size())
#define ld long double
#define db double
#define vll vector<ll>
#define all(x) x.begin(), x.end()
#define cnt_bit(a) __popcount(static_cast<unsigned long long>(a))
#define vint vector<int>
#define FOR(i, x, n) for(ll i = x; i < n; ++i)
#define rz resize
#define DIM 200007
mt19937 rng(1488);
ll randll(ll l, ll r){return uniform_int_distribution<ll>(l, r)(rng);}

ll n,m;
vector<vll> ms, dp;
ll p[DIM];

bool check(ll i, ll j) {
    if (i>=n || j >= m || j < 0 || i < 0) return 0;
    return 1;
}

int main() {
    speed;
    cin >> n >> m;
    ms.rz(n);
    dp.rz(n);
    FOR(i, 0, n) {
        ms[i].rz(m);
        dp[i].resize(m, INF);
        FOR(j, 0, m) {
            cin >> ms[i][j];
        }
    }
    FOR(i, 0, n+m-1) cin >> p[i];
    dp[n-1][m-1] = 0;
    for (ll i = n-1; i >= 0; --i) {
        for (ll j = m-1; j >= 0; --j) {
            if (check(i+1, j)) dp[i][j] = min(dp[i][j], dp[i+1][j]);
            if (check(i, j+1)) dp[i][j] = min(dp[i][j], dp[i][j+1]);
            dp[i][j] += p[i+j] - ms[i][j];
            dp[i][j] = max(dp[i][j], 0ll);
        }
    }

    cout << dp[0][0] << endl;
    return 0;
}

Submission Info

Judge Result