Submission #3005722

---

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;
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);
    }
}

bool searchl()
{
    lint maxtmp = res;
    int marg = -1;
    REP(m, M) {
        int ltmp = argmax[m][0];
        lint sum = X[ltmp] - X[r];
        REP(ms, M) {
            sum += B[*lower_bound(argmax[ms].begin(), argmax[ms].end(), ltmp)][ms];
        }
        if (sum >= maxtmp) maxtmp = sum, marg = m;
    }

    bool flg = false;
    if (marg >= 0) {
        lint ltmp = argmax[marg][0];
        if (ltmp > l) flg = true;
        l = ltmp;
        res = maxtmp;
        REP(m, M) while (argmax[m][0] < l) argmax[m].pop_front();
    }
    return flg;
}


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