Submission #3005749

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)

int N, M;
constexpr int Nmax = 5000;
constexpr int Mmax = 200;

array<lint, Nmax> X;
array<array<lint, Mmax>, Nmax> B;

array<deque<int>, Mmax> argmax;
int l, r;

lint res;

using pint = pair<int, int>;
map<pint, lint> results;

void increment_r()
{
    r++;
    REP(m, M)
    {
        while (argmax[m].size() && B[argmax[m].back()][m] <= B[r][m]) argmax[m].pop_back();
        argmax[m].push_back(r);
    }

    lint res_tmp = X[l] - X[r];
    REP(m, M) res_tmp += B[argmax[m][0]][m];
    results[pint(l, r)] = res_tmp;
    res = max(res, res_tmp);
}

bool searchl()
{
    REP(m, M) {
        int ltmp = argmax[m][0];
        if (results.count(pint(ltmp, r))) continue;
        lint sum = X[ltmp] - X[r];
        REP(ms, M) {
            sum += B[*lower_bound(argmax[ms].begin(), argmax[ms].end(), ltmp)][ms];
        }
        results[pint(ltmp, r)] = sum;
        if (sum >= res) {
            l = ltmp;
            REP(m, M) while (argmax[m][0] < l) argmax[m].pop_front();
            return true;
        }
    }
    return false;
}


int main()
{
    cin >> N >> M;
    X[0] = 0;
    FOR(i, 1, N) {
        lint tmp;
        cin >> tmp;
        X[i] = X[i - 1] + tmp;
    }
    REP(i, N) REP(j, M) cin >> B[i][j];

    l = 0, r = 0; // closed [l, r]
    argmax.fill(deque<int>{0});
    res = accumulate(B[0].begin(), B[0].end(), 0LL);
    while (r < N - 1) {
        increment_r();
        while (searchl()) {}
    }
    cout << res << endl;
}

Submission Info

Judge Result