Submission #1033803

#TimeUsernameProblemLanguageResultExecution timeMemory
1033803denislavMaxcomp (info1cup18_maxcomp)C++17
100 / 100
89 ms32684 KiB
# include <iostream> # include <algorithm> using namespace std; const long long INF=1e18; const int MAX=1e3+11; int n,m; long long a[MAX][MAX]; long long mini[MAX][MAX]; long long maxi[MAX][MAX]; void read() { cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) cin>>a[i][j]; } } void reset() { for(int i=0;i<=n;i++) { for(int j=0;j<=m;j++) { mini[i][j]=INF; maxi[i][j]-=INF; } } } long long get_ans() { reset(); long long ans=-1; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { mini[i][j]=min(mini[i][j-1],mini[i-1][j]); mini[i][j]=min(mini[i][j],a[i][j]-i-j); maxi[i][j]=max(maxi[i][j-1],maxi[i-1][j]); maxi[i][j]=max(maxi[i][j],a[i][j]+i+j); ans=max(ans,a[i][j]-i-j-mini[i][j]); ans=max(ans,maxi[i][j]-i-j-a[i][j]); //cout<<i<<" "<<j<<":"<<mini[i][j]<<" "<<maxi[i][j]<<"\n"; } } //cout<<"->"<<ans<<"\n"; return ans; } void solve() { long long ans=0; ans=max(ans,get_ans()); for(int i=1;i<=n;i++) reverse(a[i]+1,a[i]+1+m); ans=max(ans,get_ans()); cout<<ans-1<<"\n"; } int main() { ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); read(); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...