oj.uz

Submission #76577

# Submission time Handle Problem Language Result Execution time Memory
76577 2018-09-14T21:57:12 Z Vardanyan Maxcomp (info1cup18_maxcomp) C++14
100 / 100
 220 ms 70952 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 556 KB Output is correct
3 Correct 2 ms 628 KB Output is correct
4 Correct 2 ms 628 KB Output is correct
5 Correct 2 ms 628 KB Output is correct
6 Correct 2 ms 676 KB Output is correct
7 Correct 2 ms 680 KB Output is correct
8 Correct 2 ms 680 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 680 KB Output is correct
2 Correct 2 ms 680 KB Output is correct
3 Correct 2 ms 680 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 556 KB Output is correct
3 Correct 2 ms 628 KB Output is correct
4 Correct 2 ms 628 KB Output is correct
5 Correct 2 ms 628 KB Output is correct
6 Correct 2 ms 676 KB Output is correct
7 Correct 2 ms 680 KB Output is correct
8 Correct 2 ms 680 KB Output is correct
9 Correct 3 ms 1504 KB Output is correct
10 Correct 3 ms 1504 KB Output is correct
11 Correct 3 ms 1532 KB Output is correct
12 Correct 3 ms 1532 KB Output is correct
13 Correct 3 ms 1532 KB Output is correct
14 Correct 3 ms 1532 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 556 KB Output is correct
3 Correct 2 ms 628 KB Output is correct
4 Correct 2 ms 628 KB Output is correct
5 Correct 2 ms 628 KB Output is correct
6 Correct 2 ms 676 KB Output is correct
7 Correct 2 ms 680 KB Output is correct
8 Correct 2 ms 680 KB Output is correct
9 Correct 2 ms 680 KB Output is correct
10 Correct 2 ms 680 KB Output is correct
11 Correct 2 ms 680 KB Output is correct
12 Correct 3 ms 1504 KB Output is correct
13 Correct 3 ms 1504 KB Output is correct
14 Correct 3 ms 1532 KB Output is correct
15 Correct 3 ms 1532 KB Output is correct
16 Correct 3 ms 1532 KB Output is correct
17 Correct 3 ms 1532 KB Output is correct
18 Correct 220 ms 20352 KB Output is correct
19 Correct 215 ms 28732 KB Output is correct
20 Correct 195 ms 37064 KB Output is correct
21 Correct 210 ms 45548 KB Output is correct
22 Correct 209 ms 54140 KB Output is correct
23 Correct 204 ms 62664 KB Output is correct
24 Correct 169 ms 70952 KB Output is correct