Submission #11453060

---

Source Code Expand

#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<map>
#include<bitset>
#include<stack>
#include<queue>
#include<set>
#include<cmath>
#include<vector>

using namespace std;

#define bomb exit(1)
#define INF 1000000000
#define LINF 1000000000000000000ll
#define pprint(x) print(x),putchar(' ')
#define fprint(x) print(x),putchar('\n')
#define EE(x); struct edge { int nxt,to,w; }e[M << 1]; int head[N],cnt = x ^ 1;\
	void add(int u,int v,int w = 0) { e[++cnt].w = w,e[cnt].to = v,e[cnt].nxt = head[u];head[u] = cnt; }\
	void add_edge(int u,int v,int w = 0) { add(u,v,w),add(v,u,w * x); }
#define Mod(x) ((x) >= mod ? x - mod : x)
#define eps 0.00000001
#define sqr(x) ((x) * (x))
//#define getchar() (SS == TT && (TT = (SS = BB) + fread(BB,1,1 << 15,stdin),TT == SS) ? EOF : *SS++)
//char BB[1 << 15],*SS = BB,*TT = BB;
inline long long read()
{
	long long x = 0;int f = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') f = -1;
	for(;isdigit(ch);ch = getchar()) x = x * 10 + (ch ^ 48);
	return x * f;
}
void print(long long x)
{
	if(x < 0) putchar('-'),x = -x;
	if(x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
long long gcd(long long a,long long b) { return b ? gcd(b,a % b) : a; }

const int N = 5010,M = 300;
int n,m;
long long sum[N],f[N],ans;
int a[N][M],lg[N],st[M][N][20];
void init()
{
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= m;j++)
			st[j][i][0] = read();
	lg[0] = -1;
	for(int i = 1;i <= n;i++) lg[i] = lg[i >> 1] + 1;
	for(int p = 1;p <= m;p++)
		for(int j = 1;j < 20;j++)
			for(int i = 1;i <= n - (1 << j) + 1;i++)
				st[p][i][j] = max(st[p][i][j - 1],st[p][i + (1 << j - 1)][j - 1]);
}
int query(int i,int l,int r)
{
	int k = lg[r - l + 1];
	return max(st[i][l][k],st[i][r - (1 << k) + 1][k]);
}
void solve(int l,int r,int L,int R)
{
	if(l > r) return;
	int mid = l + r >> 1;
	long long ans = 0,pos;
	for(int i = L;i <= min(mid,R);i++)
	{
		long long now = sum[i] - sum[mid];
		for(int j = 1;j <= m;j++)
			now += query(j,i,mid);
		if(now > ans) ans = now,pos = i;
	}
	f[mid] = ans;
	solve(l,mid - 1,L,pos),solve(mid + 1,r,pos,R);
}

int main()
{
	n = read(),m = read();
	for(int i = 2;i <= n;i++) sum[i] = sum[i - 1] + read();
	init();
	solve(1,n,1,n);
	for(int i = 1;i <= n;i++) ans = max(ans,f[i]);
	fprint(ans);
	return 0;
}

Submission Info

Judge Result