oj.uz

Submission #410719

# Submission time Handle Problem Language Result Execution time Memory
410719 2021-05-23T12:35:17 Z nichke Maxcomp (info1cup18_maxcomp) C++14
100 / 100
 275 ms 338964 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 282988 KB Output is correct
2 Correct 114 ms 282992 KB Output is correct
3 Correct 117 ms 283056 KB Output is correct
4 Correct 123 ms 283028 KB Output is correct
5 Correct 115 ms 283052 KB Output is correct
6 Correct 117 ms 282952 KB Output is correct
7 Correct 116 ms 283036 KB Output is correct
8 Correct 116 ms 282984 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 283076 KB Output is correct
2 Correct 114 ms 283076 KB Output is correct
3 Correct 116 ms 282980 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 282988 KB Output is correct
2 Correct 114 ms 282992 KB Output is correct
3 Correct 117 ms 283056 KB Output is correct
4 Correct 123 ms 283028 KB Output is correct
5 Correct 115 ms 283052 KB Output is correct
6 Correct 117 ms 282952 KB Output is correct
7 Correct 116 ms 283036 KB Output is correct
8 Correct 116 ms 282984 KB Output is correct
9 Correct 115 ms 283516 KB Output is correct
10 Correct 116 ms 283444 KB Output is correct
11 Correct 115 ms 283448 KB Output is correct
12 Correct 117 ms 283456 KB Output is correct
13 Correct 117 ms 283504 KB Output is correct
14 Correct 116 ms 283644 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 282988 KB Output is correct
2 Correct 114 ms 282992 KB Output is correct
3 Correct 117 ms 283056 KB Output is correct
4 Correct 123 ms 283028 KB Output is correct
5 Correct 115 ms 283052 KB Output is correct
6 Correct 117 ms 282952 KB Output is correct
7 Correct 116 ms 283036 KB Output is correct
8 Correct 116 ms 282984 KB Output is correct
9 Correct 114 ms 283076 KB Output is correct
10 Correct 114 ms 283076 KB Output is correct
11 Correct 116 ms 282980 KB Output is correct
12 Correct 115 ms 283516 KB Output is correct
13 Correct 116 ms 283444 KB Output is correct
14 Correct 115 ms 283448 KB Output is correct
15 Correct 117 ms 283456 KB Output is correct
16 Correct 117 ms 283504 KB Output is correct
17 Correct 116 ms 283644 KB Output is correct
18 Correct 269 ms 330292 KB Output is correct
19 Correct 272 ms 338964 KB Output is correct
20 Correct 263 ms 336504 KB Output is correct
21 Correct 272 ms 338904 KB Output is correct
22 Correct 275 ms 338704 KB Output is correct
23 Correct 271 ms 338756 KB Output is correct
24 Correct 267 ms 337148 KB Output is correct