Submission #1692396
Source Code Expand
#include<bits/stdc++.h>
#define N 5005
#define ll long long
using namespace std;
int n,m;
int st[N],top;
int a[N][205],l[N],r[N];
ll f[N][N];
void add(int x1,int y1,int x2,int y2,int z)
{
f[x1][y1]+=z;f[x2+1][y2+1]+=z;
f[x1][y2+1]-=z;f[x2+1][y1]-=z;
}
ll sum[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=2;i<=n;i++)
{
int tmp;scanf("%d",&tmp);
sum[i]=sum[i-1]+tmp;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);
}
}
for(int i=1;i<=m;i++)
{
memset(l,0,sizeof(l));
memset(r,0,sizeof(r));
top=0;
for(int j=1;j<=n;j++)
{
while(top&&a[st[top]][i]<=a[j][i])r[st[top--]]=j;
st[++top]=j;
}
while(top)r[st[top]]=n+1,top--;
for(int j=n;j>=1;j--)
{
while(top&&a[st[top]][i]<a[j][i])l[st[top--]]=j;
st[++top]=j;
}
for(int j=1;j<=n;j++)
{
add(l[j]+1,j,j,r[j]-1,a[j][i]);
}
}
ll ans=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
f[i][j]+=-f[i-1][j-1]+f[i-1][j]+f[i][j-1];
if(j>=i)ans=max(ans,f[i][j]-sum[j]+sum[i]);
}
}
cout<<ans<<endl;
return 0;
}
Submission Info
Submission Time
2017-10-18 20:22:09+0900
Task
F - Yakiniku Restaurants
User
SD_le
Language
C++14 (GCC 5.4.1)
Score
1000
Code Size
1366 Byte
Status
AC
Exec Time
317 ms
Memory
200064 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:17:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&m);
^
./Main.cpp:20:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int tmp;scanf("%d",&tmp);
^
./Main.cpp:27:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a[i][j]);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
1000 / 1000
Status
Set Name
Test Cases
Sample
sample_01.txt, sample_02.txt
All
sample_01.txt, sample_02.txt, subtask_1_dense_max_01.txt, subtask_1_dense_max_02.txt, subtask_1_dense_max_03.txt, subtask_1_dense_max_04.txt, subtask_1_dense_rand_01.txt, subtask_1_dense_rand_02.txt, subtask_1_dense_rand_03.txt, subtask_1_dense_rand_04.txt, subtask_1_max_01.txt, subtask_1_max_02.txt, subtask_1_max_03.txt, subtask_1_max_04.txt, subtask_1_min_01.txt, subtask_1_min_02.txt, subtask_1_rand_01.txt, subtask_1_rand_02.txt, subtask_1_rand_03.txt, subtask_1_rand_04.txt, subtask_1_widemax_01.txt, subtask_1_widemax_02.txt, subtask_1_widemax_03.txt, subtask_1_widemax_04.txt, subtask_1_widemax_05.txt, subtask_1_widemax_06.txt, subtask_1_widemax_07.txt, subtask_1_widemax_08.txt, subtask_1_widemax_09.txt, subtask_1_widemax_10.txt
Case Name
Status
Exec Time
Memory
sample_01.txt
AC
2 ms
2304 KB
sample_02.txt
AC
2 ms
2304 KB
subtask_1_dense_max_01.txt
AC
317 ms
199936 KB
subtask_1_dense_max_02.txt
AC
268 ms
200064 KB
subtask_1_dense_max_03.txt
AC
267 ms
199936 KB
subtask_1_dense_max_04.txt
AC
268 ms
199936 KB
subtask_1_dense_rand_01.txt
AC
165 ms
141056 KB
subtask_1_dense_rand_02.txt
AC
181 ms
149504 KB
subtask_1_dense_rand_03.txt
AC
15 ms
31488 KB
subtask_1_dense_rand_04.txt
AC
56 ms
81152 KB
subtask_1_max_01.txt
AC
267 ms
199936 KB
subtask_1_max_02.txt
AC
267 ms
199936 KB
subtask_1_max_03.txt
AC
267 ms
199936 KB
subtask_1_max_04.txt
AC
267 ms
200064 KB
subtask_1_min_01.txt
AC
2 ms
2304 KB
subtask_1_min_02.txt
AC
2 ms
2304 KB
subtask_1_rand_01.txt
AC
39 ms
39680 KB
subtask_1_rand_02.txt
AC
43 ms
76928 KB
subtask_1_rand_03.txt
AC
49 ms
60416 KB
subtask_1_rand_04.txt
AC
136 ms
189568 KB
subtask_1_widemax_01.txt
AC
267 ms
200064 KB
subtask_1_widemax_02.txt
AC
267 ms
199936 KB
subtask_1_widemax_03.txt
AC
266 ms
199936 KB
subtask_1_widemax_04.txt
AC
267 ms
200064 KB
subtask_1_widemax_05.txt
AC
267 ms
199936 KB
subtask_1_widemax_06.txt
AC
268 ms
200064 KB
subtask_1_widemax_07.txt
AC
268 ms
200064 KB
subtask_1_widemax_08.txt
AC
267 ms
199936 KB
subtask_1_widemax_09.txt
AC
267 ms
199936 KB
subtask_1_widemax_10.txt
AC
267 ms
199936 KB