Submission #516486

#	Time	Username	Problem	Language	Result	Execution time	Memory
516486		Ronin13	Maxcomp (info1cup18_maxcomp)	C++14	100 / 100	407 ms	28684 KiB

maxcomp

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define epb emplace_back
#define inf 1e9+1
#define linf 1e18+1
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;

int main(){
    int n;cin>>n;
    int m;cin>>m;
    int ans=-inf;
    int a[n+1][m+1];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    int mx1[n+2][m+2],mx2[n+2][m+2],mx3[n+2][m+2],mx4[n+2][m+2];
    for(int i=0;i<=n+1;i++){
        for(int j=0;j<=m+1;j++){
            mx1[i][j]=mx2[i][j]=mx3[i][j]=mx4[i][j]=-inf;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            mx1[i][j]=max({mx1[i-1][j],mx1[i][j-1],a[i][j]+i+j});
        }
    }
    for(int i=n;i>=1;i--){
        for(int j=1;j<=m;j++){
            mx2[i][j]=max({mx2[i+1][j],mx2[i][j-1],a[i][j]+j-i});
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=m;j>=1;j--){
            mx3[i][j]=max({mx3[i-1][j],mx3[i][j+1],a[i][j]-j+i});
        }
    }
    for(int i=n;i>=1;i--){
        for(int j=m;j>=1;j--){
            mx4[i][j]=max({mx4[i+1][j],mx4[i][j+1],a[i][j]-i-j});
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){

            ans=max(ans,mx1[i][j]-a[i][j]-i-j);
            ans=max(ans,mx2[i][j]-a[i][j]-j+i);
            ans=max(ans,mx3[i][j]-a[i][j]-i+j);
            ans=max(ans,mx4[i][j]-a[i][j]+i+j);
        }

    }
    cout<<ans-1;
    return 0;
}

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