Submission #1865004

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define rep(i, s, t) for(int i = (s); i <= (t); i++)
#define dwn(i, s, t) for(int i = (s); i >= (t); i--)

int read() {
	int x = 0, f = 1; char c = getchar();
	while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
	while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
	return x * f;
}

#define maxn 5010
#define maxm 210
#define LL long long

int n, m, A[maxn], d[maxn][maxm], St[maxm][maxn], top[maxm];
LL add[maxn];

int main() {
	
	n = read(); m = read();
	rep(i, 1, n - 1) A[i] = read();
	rep(i, 1, n) rep(j, 1, m) d[i][j] = read();
	
	LL ans = 0;
	dwn(l, n, 1) {
		LL dis = 0, sum = 0;
		rep(i, 1, m) {
			while(top[i] && d[St[i][top[i]]][i] <= d[l][i]) {
				if(top[i] > 1) add[St[i][top[i]-1]] -= d[St[i][top[i]-1]][i] - d[St[i][top[i]]][i];
				top[i]--;
			}
			St[i][++top[i]] = l;
			if(top[i] > 1) add[St[i][top[i]-1]] += d[St[i][top[i]-1]][i] - d[l][i];
			sum += d[l][i];
		}
		rep(r, l, n) sum += add[r], ans = max(ans, sum - dis), dis += A[r];
	}
	
	printf("%lld\n", ans);
	
	return 0;
}

Submission Info

Judge Result