Submission #1864403

---

Source Code Expand

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=5050;
const int MAXM=202;
inline int read()
{
	int x=0,t=1,c;
	while(!isdigit(c=getchar()))if(c=='-')t=-1;
	while(isdigit(c))x=x*10+c-'0',c=getchar();
	return x*t;
}
int n,m;
int maxv[MAXM][15][MAXN];
int d[MAXM][MAXN];
int Log[MAXN];
int lenth[MAXN];
long long pos[MAXN];
void Init()
{
	Log[1]=0;
	for(int i=2;i<=n;i++)Log[i]=Log[i>>1]+1;
	for(int k=0;k<m;k++)
	{
		for(int i=0;i<n;i++)maxv[k][0][i]=d[k][i];
		for(int i=1;i<=Log[n];i++)
		{
			for(int j=0;j<n;j++)
			{
				maxv[k][i][j]=maxv[k][i-1][j];
				if(j+(1<<(i-1))<n)maxv[k][i][j]=max(maxv[k][i][j],maxv[k][i-1][j+(1<<(i-1))]);
			}
		}
	}
}
int Query(int k,int L,int R)
{
	int f=Log[R-L+1];
	return max(maxv[k][f][L],maxv[k][f][R-(1<<f)+1]);
}
long long ans2=0;
bool vis[MAXN][MAXN];
long long Eva(int L,int R)
{
	if(vis[L][R])return -1;
	vis[L][R]=1;
	long long ret=0;
	ret=0;
	for(int i=0;i<m;i++)ret+=Query(i,L,R);
	ret-=pos[R]-pos[L];
	ans2=max(ans2,ret);
	return ret;
}
int Rand()
{
	return (rand()<<15)|rand();
}
int Rand(int L,int R)
{
	return Rand()%(R-L+1)+L;
}
class State
{
public:
	int L,R;
	long long v;
	State(int _l=0,int _r=0)
	{
		if(_l>_r)swap(_l,_r);
		L=_l,R=_r;
		v=Eva(L,R);
	}
	bool operator < (const State &b) const
	{
		return v>b.v;
	}
}state[MAXN];
int cnts=0;
const int REMAIN=50;
void Solve()
{
	for(int i=0;i<REMAIN;i++)
	{
		state[cnts]=State(Rand()%n,Rand()%n);
		if(state[cnts].v!=-1)cnts++;
	}
	for(int i=max(10,n/25);i>0;i--)
	{
		for(int j=0;j<REMAIN;j++)
		{
			for(int k=0;k<99;k++)
			{
				state[cnts]=State(Rand(max(state[j].L-i,0),min(state[j].L+i,n-1)),Rand(max(state[j].R-i,0),min(state[j].R+i,n-1)));
				if(state[cnts].v!=-1)cnts++;
			}
		}
		sort(state,state+cnts);
		cnts=min(cnts,REMAIN);
	}
}
int main()
{
	srand(20162503);
	n=read(),m=read();
	for(int i=1;i<n;i++)lenth[i]=read();
	for(int i=1;i<n;i++)pos[i]=pos[i-1]+lenth[i];
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			d[j][i]=read();
	Init();
	if(n<=0)
	{
		long long ans=0;
		for(int i=0;i<n;i++)
			for(int j=i;j<n;j++)
				ans=max(ans,Eva(i,j));
		printf("%lld",ans);
	}
	else
	{
		Solve();
		printf("%lld",ans2);
	}
}
/*
3 4
1 4
2 2 5 1
1 3 3 2
2 2 5 1
*/

Submission Info

Judge Result