Submission #1161545

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161545		itaykarny	Maxcomp (info1cup18_maxcomp)	C++20	100 / 100	74 ms	23880 KiB

maxcomp

#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<queue>

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;



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

	ll n, m;
	cin >> n >> m;
	vvll matrix(n, vll(m));
	for (ll i = 0; i < n; i++) {
		for (ll j = 0; j < m; j++) {
			cin >> matrix[i][j];
		}
	}
	ll ans = -1;
	vvll min_ele(n, vll(m, 1e18)), max_ele(n, vll(m, -2));
	for (ll i = 0; i < n; i++) {
		for (ll j = 0; j < m; j++) {
			if (i > 0) {
				min_ele[i][j] = min_ele[i - 1][j];
				max_ele[i][j] = max_ele[i - 1][j];
			}
			if (j > 0) {
				min_ele[i][j] = min(min_ele[i][j], min_ele[i][j - 1]);
				max_ele[i][j] = max(max_ele[i][j], max_ele[i][j - 1]);
			}
			min_ele[i][j] = min(min_ele[i][j], matrix[i][j] - i - j );
			max_ele[i][j] = max(max_ele[i][j], matrix[i][j] + i + j);
			ans = max(ans, (matrix[i][j] - i - j) - min_ele[i][j] - 1);
			ans = max(ans, max_ele[i][j] - (matrix[i][j] + i + j) - 1);
		}
	}
	min_ele.clear(), max_ele.clear();
	min_ele.resize(n, vll(m, 1e18)), max_ele.resize(n, vll(m,-2));
	for (ll i = n - 1; i >= 0; i--) {
		for (ll j = 0; j < m; j++) {
			if (i < n-1) {
				min_ele[i][j] = min_ele[i + 1][j];
				max_ele[i][j] = max_ele[i + 1][j];
			}
			if (j > 0) {
				min_ele[i][j] = min(min_ele[i][j], min_ele[i][j - 1]);
				max_ele[i][j] = max(max_ele[i][j], max_ele[i][j - 1]);
			}
			min_ele[i][j] = min(min_ele[i][j], matrix[i][j] + i - j);
			max_ele[i][j] = max(max_ele[i][j], matrix[i][j] - i + j);
			ans = max(ans, (matrix[i][j] + i - j) - min_ele[i][j] - 1);
			ans = max(ans, max_ele[i][j] - (matrix[i][j] - i + j) - 1);
		}
	}
	cout << ans << endl;
}

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