Submission #1161542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161542		yonatanl	Maxcomp (info1cup18_maxcomp)	C++20	100 / 100	88 ms	31896 KiB

maxcomp

#include <iostream>
#include <vector>
#include <algorithm>

#define rep(i, s, e) for (ll i = s; i < e; i++)
#define upmax(a, b) a = max(a, b)

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;

ll calc(vvll& arr, ll n, ll m) {
	vvll minV(n, vll(m)), maxV(n, vll(m));
	vvll ans(n, vll(m));
	maxV[0][0] = arr[0][0];
	minV[0][0] = arr[0][0];
	rep(i, 1, n) {
		minV[i][0] = min(minV[i - 1][0], arr[i][0] - i);
		maxV[i][0] = max(maxV[i - 1][0], arr[i][0] + i);
		ans[i][0] = max(arr[i][0] - i - minV[i][0], maxV[i][0] - arr[i][0] - i);
	}
	rep(j, 1, m) {
		minV[0][j] = min(minV[0][j - 1], arr[0][j] - j);
		maxV[0][j] = max(maxV[0][j - 1], arr[0][j] + j);
		ans[0][j] = max(arr[0][j] - j - minV[0][j], maxV[0][j] - arr[0][j] - j);
	}
	rep(i, 1, n) {
		rep(j, 1, m) {
			minV[i][j] = min(arr[i][j] - i - j, min(minV[i - 1][j], minV[i][j - 1]));
			maxV[i][j] = max(arr[i][j] + i + j, max(maxV[i - 1][j], maxV[i][j - 1]));
			ans[i][j] = max(arr[i][j] - i - j - minV[i][j], maxV[i][j] - arr[i][j] - i - j);
		}
	}
	ll res = -1;
	rep(i, 0, n) {
		rep(j, 0, m) {
			upmax(res, ans[i][j]);
		}
	}
	return res;
}

void solve() {
	ll n, m;
	cin >> n >> m;
	vvll arr(n, vll(m));
	rep(i, 0, n) {
		rep(j, 0, m) {
			cin >> arr[i][j];
		}
	}
	ll res = calc(arr, n, m);
	rep(i, 0, n) {
		reverse(arr[i].begin(), arr[i].end());
	}
	upmax(res, calc(arr, n, m));
	cout << res - 1 << endl;
}

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

	solve();
}

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