Submission #916885

#	Time	Username	Problem	Language	Result	Execution time	Memory
916885		andrei_iorgulescu	Maxcomp (info1cup18_maxcomp)	C++14	100 / 100	91 ms	21316 KiB

maxcomp

#include <bits/stdc++.h>

using namespace std;

int n,m,a[1005][1005];
int bestmic[1005][1005],bestmare[1005][1005];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    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++)
        {
            bestmare[i][j] = bestmic[i][j] = -1e9;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        int mx = -1e9;
        int mn = -2e9;
        for (int j = 1; j <= m; j++)
        {
            mx = max(mx,a[i][j] + j);
            mn = max(mn,-a[i][j] + j);
            bestmare[i][j] = max(bestmare[i][j],mx - j);
            bestmic[i][j] = max(bestmic[i][j],mn - j);
        }
        mx = -1e9;
        mn = -2e9;
        for (int j = m; j >= 1; j--)
        {
            mx = max(mx,a[i][j] - j);
            mn = max(mn,-a[i][j] - j);
            bestmare[i][j] = max(bestmare[i][j],mx + j);
            bestmic[i][j] = max(bestmic[i][j],mn + j);
        }
    }
    for (int j = 1; j <= m; j++)
    {
        int mx = -1e9;
        int mn = -2e9;
        for (int i = 1; i <= n; i++)
        {
            mx = max(mx,a[i][j] + i);
            mn = max(mn,-a[i][j] + i);
            bestmare[i][j] = max(bestmare[i][j],mx - i);
            bestmic[i][j] = max(bestmic[i][j],mn - i);
        }
        mx = -1e9;
        mn = -2e9;
        for (int i = n; i >= 1; i--)
        {
            mx = max(mx,a[i][j] - i);
            mn = max(mn,-a[i][j] - i);
            bestmare[i][j] = max(bestmare[i][j],mx + i);
            bestmic[i][j] = max(bestmic[i][j],mn + i);
        }
    }
    /*for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            cout << bestmare[i][j] << ' ';
        cout << '\n';
    }
    cout << '\n';
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            cout << bestmic[i][j] << ' ';
        cout << '\n';
    }*/
    int ans = -1e9;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            ans = max(ans,bestmare[i][j] + bestmic[i][j] - 1);
    cout << ans;
    return 0;
}

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