Submission #76577

#	Time	Username	Problem	Language	Result	Execution time	Memory
76577		Vardanyan	Maxcomp (info1cup18_maxcomp)	C++14	100 / 100	220 ms	70952 KiB

maxcomp

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int a[N][N];
int dp1[N][N];
int dp2[N][N];
int dp3[N][N];
int dp4[N][N];
int ans = -2*1000*1000*1000-5;
void update(int i,int j){
    ans = max(ans,a[i][j]-i-j+dp1[i][j]);
    ans = max(ans,a[i][j]-i+j+dp2[i][j]);
    ans = max(ans,a[i][j]+i-j+dp3[i][j]);
    ans = max(ans,a[i][j]+i+j+dp4[i][j]);
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    /*for(int i = 0;i<=n+2;i++){
        for(int j = 0;j<=m+2;j++){
            dp1[i][j] = dp2[i][j] = dp3[i][j] = dp4[i][j] = -1000000007;
        }
    }*/
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=m;j++) scanf("%d",&a[i][j]);
    /*
    memset(dp1,-1,sizeof(dp1));
    memset(dp2,-1,sizeof(dp2));
    memset(dp3,-1,sizeof(dp3));
    memset(dp4,-1,sizeof(dp4));*/
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            dp1[i][j] = ans;
            if(i>1) dp1[i][j] = max(dp1[i][j],dp1[i-1][j]);
            if(j>1) dp1[i][j] = max(dp1[i][j],dp1[i][j-1]);
            dp1[i][j] = max(dp1[i][j],-a[i][j]+i+j);
        }
    }
    for(int i = 1;i<=n;i++){
        for(int j = m;j>=1;j--){
            dp2[i][j] = ans;
            if(i>1) dp2[i][j] = max(dp2[i][j],dp2[i-1][j]);
            if(j<m) dp2[i][j] = max(dp2[i][j],dp2[i][j+1]);
            dp2[i][j] = max(dp2[i][j],-a[i][j]+i-j);
        }
    }
    for(int i = n;i>=1;i--){
        for(int j  = 1;j<=m;j++){
            dp3[i][j] = ans;
            if(i<n) dp3[i][j] = max(dp3[i][j],dp3[i+1][j]);
            if(j>1) dp3[i][j] = max(dp3[i][j],dp3[i][j-1]);
            dp3[i][j] = max(dp3[i][j],-a[i][j]-i+j);
        }
    }
    for(int i = n;i>=1;i--){
        for(int j = m;j>=1;j--){
            dp4[i][j] = ans;
            if(i<n) dp4[i][j] = max(dp4[i][j],dp4[i+1][j]);
            if(j<m) dp4[i][j] = max(dp4[i][j],dp4[i][j+1]);
            dp4[i][j] = max(dp4[i][j],-a[i][j]-i-j);
        }
    }
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            update(i,j);
        }
    }
    ans--;
    cout<<ans<<endl;
    return 0;
}

Compilation message (stderr)

maxcomp.cpp: In function 'int main()':
maxcomp.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
maxcomp.cpp:25:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         for(int j = 1;j<=m;j++) scanf("%d",&a[i][j]);
                                 ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40