Submission #97805

#	Time	Username	Problem	Language	Result	Execution time	Memory
97805		IrishWhiskey	Maxcomp (info1cup18_maxcomp)	C++11	100 / 100	211 ms	40568 KiB

maxcomp

#include <bits/stdc++.h>
#define MAXN 1005

typedef long long int ll;

int N, M;
ll A[MAXN][MAXN], cnt[4][MAXN][MAXN];

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);

    std::cin >> N >> M;
    for(int k=0; k<4; k++)
        for(int i=0; i<=N+3; i++)
            for(int j=0; j<=M+3; j++)
                cnt[k][i][j] = INT_MIN;

    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=M; j++)
        {
            std::cin >> A[i][j];
            cnt[0][i][j] = std::max(-A[i][j]+i+j, std::max(cnt[0][i-1][j], cnt[0][i][j-1]));
        }
    }

    for(int i=1; i<=N; i++)
        for(int j=M; j>0; j--)
            cnt[1][i][j] = std::max(-A[i][j]+i-j, std::max(cnt[1][i-1][j], cnt[1][i][j+1]));

    for(int i=N; i>0; i--)
        for(int j=1; j<=M; j++)
            cnt[2][i][j] = std::max(-A[i][j]-i+j, std::max(cnt[2][i+1][j], cnt[2][i][j-1]));

    for(int i=N; i>0; i--)
        for(int j=M; j>0; j--)
            cnt[3][i][j] = std::max(-A[i][j]-i-j, std::max(cnt[3][i+1][j], cnt[3][i][j+1]));

    ll ans=INT_MIN;
    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=M; j++)
        {
            ans = std::max(ans, A[i][j]-i-j+std::max(cnt[0][i-1][j], cnt[0][i][j-1]));
            ans = std::max(ans, A[i][j]-i+j+cnt[1][i][j+1]);
            ans = std::max(ans, A[i][j]+i-j+cnt[2][i+1][j]);
            ans = std::max(ans, A[i][j]+i+j+cnt[3][i+1][j+1]);
        }
    }

    std::cout << ans-1 << "\n";

    return 0;
}

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