Submission #1161537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161537		yonatanl	Maxcomp (info1cup18_maxcomp)	C++20	15 / 100	0 ms	328 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] = max(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] - 1, maxV[i][0] - arr[i][0] - i - 1);
	}
	rep(j, 1, m) {
		minV[0][j] = max(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] - 1, maxV[0][j] - arr[0][j] - j - 1);
	}
	rep(i, 1, n) {
		rep(j, 1, m) {
			minV[i][j] = max(-arr[i][j] + i + j, max(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] - 1, maxV[i][j] - arr[i][j] - i - j - 1);
		}
	}
	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 << endl;
}

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

	solve();
}

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