Submission #197476

#	Time	Username	Problem	Language	Result	Execution time	Memory
197476		Vladikus004	Maxcomp (info1cup18_maxcomp)	C++14	100 / 100	194 ms	48264 KiB

maxcomp

#include <bits/stdc++.h>
#define int long long
#define inf 2e9
#define ff first
#define ss second
#define all(v) v.begin() , v.end()
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
const int N = 1000 + 3;
int a[N][N], dp1[N][N], dp2[N][N], dp3[N][N], dp4[N][N];
int n, m;

int32_t main()
{
    #ifdef VBH
        freopen("input.txt" , "r" , stdin);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];


    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dp1[i][j] = max(a[i][j], max(dp1[i - 1][j], dp1[i][j - 1]) - 1);

    for (int i = n; i > 0; i--)
        for (int j = m; j > 0; j--)
            dp2[i][j] = max(a[i][j], max(dp2[i + 1][j], dp2[i][j + 1]) - 1);

    for (int i = 1; i <= n; i++)
        for (int j = m; j > 0; j--)
            dp3[i][j] = max(a[i][j], max(dp3[i - 1][j], dp3[i][j + 1]) - 1);

    for (int i = n; i > 0; i--)
        for (int j = 1; j <= m; j++)
            dp4[i][j] = max(a[i][j], max(dp4[i + 1][j], dp4[i][j - 1]) - 1);



    int mx = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            mx = max(mx, max(max(dp1[i][j], dp2[i][j]), max(dp3[i][j], dp4[i][j])) - a[i][j]);
    cout << mx - 1;
    return 0;
}

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