Submission #97769

#	Time	Username	Problem	Language	Result	Execution time	Memory
97769		igzi	Maxcomp (info1cup18_maxcomp)	C++17	60 / 100	520 ms	16756 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;
    }
}
return res;
}

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

void transformisi2(){
int i,j;
for(j=0;j<m;j++){
    for(i=0;i<n/2;i++){
        swap(a[i][j],a[n-i-1][j]);
    }
}
}

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

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