Submission #866473

#	Time	Username	Problem	Language	Result	Execution time	Memory
866473		aykhn	Maxcomp (info1cup18_maxcomp)	C++17	100 / 100	272 ms	49188 KiB

maxcomp

#include <bits/stdc++.h>
 
// author : aykhn
 
using namespace std;
typedef long long ll;
 
#define pb push_back
#define ins insert
#define mpr make_pair
#define all(v) v.begin(), v.end()
#define bpc __builtin_popcount
#define bpcll __builtin_popcountll
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define int ll
#define infll 0x3F3F3F3F3F3F3F3F
#define inf 0x3F3F3F3F

const int MXN = 1e3 + 5;

int n, m;
int mat[MXN][MXN];
int ul[MXN][MXN], ur[MXN][MXN], dl[MXN][MXN], dr[MXN][MXN];

signed main()
{
    cin >> n >> m;
    for (int i = 0; i < MXN; i++)
    {
        for (int j = 0; j < MXN; j++)
        {
            mat[i][j] = ul[i][j] = ur[i][j] = dl[i][j] = dr[i][j] = inf;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> mat[i][j];
            int i1 = n - i + 1;
            int j1 = m - j + 1;
            ul[i][j] = mat[i][j] - (i + j - 2);
            ur[i][j] = mat[i][j] - (i + j1 - 2);
            dl[i][j] = mat[i][j] - (i1 + j - 2);
            dr[i][j] = mat[i][j] - (i1 + j1 - 2);
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            ul[i][j] = min({ul[i - 1][j], ul[i][j - 1], ul[i][j]});
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = m; j >= 1; j--)
        {
            ur[i][j] = min({ur[i - 1][j], ur[i][j + 1], ur[i][j]});
        }
    }
    for (int i = n; i >= 1; i--)
    {
        for (int j = 1; j <= m; j++)
        {
            dl[i][j] = min({dl[i + 1][j], dl[i][j - 1], dl[i][j]});
        }
    }
    for (int i = n; i >= 1; i--)
    {
        for (int j = m; j >= 1; j--)
        {
            dr[i][j] = min({dr[i + 1][j], dr[i][j + 1], dr[i][j]});
        }
    }
    int ans = -inf;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            int i1 = n - i + 1;
            int j1 = m - j + 1;
            int mn = min({ul[i][j] + (i + j - 2), ur[i][j] + (i + j1 - 2), dl[i][j] + (i1 + j - 2), dr[i][j] + (i1 + j1 - 2)});
            mn++;
            ans = max(ans, mat[i][j] - mn);
        }
    }
    cout << ans << '\n';

}

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