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
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
AC × 2
AC × 30
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