답안 #410719

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
410719	2021-05-23T12:35:17 Z	nichke	Maxcomp (info1cup18_maxcomp)	C++14	100 / 100	275 ms	338964 KB

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.0 / 15.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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