oj.uz

Submission #97770

# Submission time Handle Problem Language Result Execution time Memory
97770 2019-02-18T11:46:14 Z igzi Maxcomp (info1cup18_maxcomp) C++17
100 / 100
 193 ms 17144 KB 
#include <bits/stdc++.h>
#define maxN 1005

using namespace std;

int a[maxN][maxN],dp[maxN][maxN],n,m,i,j;
int ans=-1;

int resi(){
int res=-1,i,j,tmp;
for(i=0;i<n;i++){
    for(j=0;j<m;j++){
        tmp=a[i][j]-i-j;
        if(i>0) tmp=min(tmp,dp[i-1][j]);
        if(j>0) tmp=min(tmp,dp[i][j-1]);
        res=max(res,a[i][j]-i-j-tmp-1);
        dp[i][j]=tmp;
    }
}
for(i=n-1;i>=0;i--){
    for(j=m-1;j>=0;j--){
        tmp=a[i][j]+i+j;
        if(i<n-1) tmp=min(tmp,dp[i+1][j]);
        if(j<m-1) tmp=min(tmp,dp[i][j+1]);
        res=max(res,a[i][j]+i+j-tmp-1);
        dp[i][j]=tmp;
    }
}
return res;
}

void transformisi(){
for(int i=0;i<n;i++) reverse(a[i],a[i]+m);
}

int main()
{
    std::ios_base::sync_with_stdio(0);
    cin>>n>>m;
    for(i=0;i<n;i++){
        for(j=0;j<m;j++){
            cin>>a[i][j];
        }
    }
    ans=max(ans,resi());
    transformisi();
    ans=max(ans,resi());
    cout<<ans<<endl;
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Correct 3 ms 768 KB Output is correct
12 Correct 4 ms 768 KB Output is correct
13 Correct 3 ms 768 KB Output is correct
14 Correct 4 ms 768 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 3 ms 768 KB Output is correct
13 Correct 1 ms 768 KB Output is correct
14 Correct 3 ms 768 KB Output is correct
15 Correct 4 ms 768 KB Output is correct
16 Correct 3 ms 768 KB Output is correct
17 Correct 4 ms 768 KB Output is correct
18 Correct 162 ms 8292 KB Output is correct
19 Correct 179 ms 16796 KB Output is correct
20 Correct 175 ms 16472 KB Output is correct
21 Correct 158 ms 16760 KB Output is correct
22 Correct 193 ms 16888 KB Output is correct
23 Correct 159 ms 16892 KB Output is correct
24 Correct 147 ms 17144 KB Output is correct