Submission #1864413

---

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], mxd[maxn][maxm], nowmx[maxm], lid[maxn];
LL mxsum[maxn];

int main() {
	srand(10);
	
	n = read(); m = read();
	rep(i, 1, n - 1) A[i] = read();
	rep(i, 1, n) rep(j, 1, m) d[i][j] = read();
	
	dwn(i, n, 1) rep(j, 1, m) mxd[i][j] = max(mxd[i+1][j], d[i][j]), mxsum[i] += mxd[i][j];
	LL ans = 0;
	rep(i, 1, n) lid[i] = i; random_shuffle(lid + 1, lid + n + 1);
	rep(L, 1, n) {
		int l = lid[L];
		memset(nowmx, 0, sizeof(nowmx));
		LL nowdis = 0;
		rep(r, l, n) {
			LL sum = 0;
			rep(i, 1, m) nowmx[i] = max(nowmx[i], d[r][i]), sum += nowmx[i];
			ans = max(ans, sum - nowdis);
			if(ans >= mxsum[l] - nowdis) break;
			nowdis += A[r];
		}
	}
	
	printf("%lld\n", ans);
	return 0;
}

Submission Info

Judge Result