Submission #97770

#	Time	Username	Problem	Language	Result	Execution time	Memory
97770		igzi	Maxcomp (info1cup18_maxcomp)	C++17	100 / 100	193 ms	17144 KiB

maxcomp

#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 / 15
• Subtask 2: 15 / 15
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40