Submission #410719

#	Time	Username	Problem	Language	Result	Execution time	Memory
410719		nichke	Maxcomp (info1cup18_maxcomp)	C++14	100 / 100	275 ms	338964 KiB

maxcomp

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

int n, m, ans = -2;
int ar[3005][3005];
int val[3005][3005][4];
int mn[3005][3005][4];

signed main() {
	ios_base::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 >> ar[i][j];
			val[i][j][0] = ar[i][j] - i - j + 1;
			val[i][j][1] = ar[i][j] - m + j - i;
			val[i][j][2] = ar[i][j] + i + j - 1;
			val[i][j][3] = ar[i][j] + m - j + i;
		}
	}
	memset(mn, 0x3f, sizeof mn);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			mn[i][j][0] = min({val[i][j][0], mn[i - 1][j][0], mn[i][j - 1][0]});
			ans = max(ans, val[i][j][0] - mn[i][j][0]);
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = m; j >= 1; j--) {
			mn[i][j][1] = min({val[i][j][1], mn[i - 1][j][1], mn[i][j + 1][1]});
			ans = max(ans, val[i][j][1] - mn[i][j][1]);
		}
	}
	for (int i = n; i >= 1; i--) {
		for (int j = m; j >= 1; j--) {
			mn[i][j][2] = min({val[i][j][2], mn[i + 1][j][2], mn[i][j + 1][2]});
			ans = max(ans, val[i][j][2] - mn[i][j][2]);
		}
	}
	for (int i = n; i >= 1; i--) {
		for (int j = 1; j <= m; j++) {
			mn[i][j][3] = min({val[i][j][3], mn[i + 1][j][3], mn[i][j - 1][3]});
			ans = max(ans, val[i][j][3] - mn[i][j][3]);
		}
	}
	cout << ans - 1 << '\n';
	return 0;
}

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