Submission #1117983

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117983		_callmelucian	Maxcomp (info1cup18_maxcomp)	C++14	100 / 100	80 ms	13384 KiB

maxcomp

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpl;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

int a[1010][1010], colPos[1010], colNeg[1010], n, m;

int solve() {
    int ans = 0;
    for (int j = 1; j <= m; j++) colPos[j] = colNeg[j] = INT_MIN;
    for (int i = 1; i <= n; i++) {
        int bestPos = INT_MIN, bestNeg = INT_MIN;
        for (int j = 1; j <= m; j++) {
            colPos[j] = max(colPos[j], a[i][j] + i + j);
            colNeg[j] = max(colNeg[j], -a[i][j] + i + j);
            bestPos = max(bestPos, colPos[j]);
            bestNeg = max(bestNeg, colNeg[j]);
            ans = max({ans, a[i][j] - i - j + bestNeg, bestPos - a[i][j] - i - j});
        }
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) cin >> a[i][j];

    int save = solve();
    for (int i = 1; i <= n; i++) reverse(a[i] + 1, a[i] + 1 + m);
    cout << max(save, solve()) - 1;

    return 0;
}

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