Submission #1864414
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();
}
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/8);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
Submission Time |
|
Task |
C - Factors of Factorial |
User |
LazyJazz |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2360 Byte |
Status |
TLE |
Exec Time |
2103 ms |
Memory |
2304 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 300 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
All |
sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_certain_01.txt, subtask_1_certain_02.txt, subtask_1_certain_03.txt, subtask_1_certain_04.txt, subtask_1_rand_01.txt, subtask_1_rand_02.txt, subtask_1_rand_03.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
TLE |
2103 ms |
2304 KB |
sample_02.txt |
TLE |
2103 ms |
2304 KB |
sample_03.txt |
TLE |
2103 ms |
2304 KB |
subtask_1_certain_01.txt |
TLE |
2103 ms |
2304 KB |
subtask_1_certain_02.txt |
TLE |
2103 ms |
2304 KB |
subtask_1_certain_03.txt |
TLE |
2103 ms |
2304 KB |
subtask_1_certain_04.txt |
TLE |
2103 ms |
2304 KB |
subtask_1_rand_01.txt |
TLE |
2103 ms |
2304 KB |
subtask_1_rand_02.txt |
TLE |
2103 ms |
2304 KB |
subtask_1_rand_03.txt |
TLE |
2103 ms |
2304 KB |