oj.uz

답안 #878863

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
878863 2023-11-25T11:06:49 Z SanguineChameleon 축구 경기장 (IOI23_soccer) C++17
100 / 100
 546 ms 176620 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;

const int maxN = 2e3 + 20;
int A[maxN][maxN];
int prv[maxN][maxN][2];
int top[maxN][maxN];
int bottom[maxN][maxN];
vector<pair<int, int>> group[maxN];
int dp[maxN][maxN];

int biggest_stadium(int N, vector<vector<int>> _A) {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			A[i][j] = _A[i - 1][j - 1];
		}
	}
	for (int i = 0; i <= N + 1; i++) {
		A[0][i] = 1;
		A[N + 1][i] = 1;
		A[i][0] = 1;
		A[i][N + 1] = 1;
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			for (int k = 0; k < 2; k++) {
				if (A[i][j] == k) {
					prv[i][j][k] = j;
				}
				else {
					prv[i][j][k] = prv[i][j - 1][k];
				}
			}
		}
	}
	for (int j = 0; j <= N; j++) {
		top[0][j] = 0;
		bottom[N + 1][j] = N + 1;
	}
	for (int i = 1; i <= N + 1; i++) {
		for (int j = 0; j <= N + 1; j++) {
			if (A[i - 1][j] == 1) {
				top[i][j] = i - 1;
			}
			else {
				top[i][j] = top[i - 1][j];
			}
		}
	}
	for (int i = N; i >= 1; i--) {
		for (int j = 0; j <= N; j++) {
			if (A[i + 1][j] == 1) {
				bottom[i][j] = i + 1;
			}
			else {
				bottom[i][j] = bottom[i + 1][j];
			}
		}
	}
	for (int i = N; i >= 1; i--) {
		for (int j = 1; j <= N; j++) {
			if (A[i][j] == 0) {
				if (A[i][j - 1] == 0) {
					top[i][j] = max(top[i][j], top[i][j - 1]);
					bottom[i][j] = min(bottom[i][j], bottom[i][j - 1]);
				}
				group[j - prv[i][j][1]].emplace_back(i, j);
			}
		}
	}
	int res = 0;
	for (int W = N; W >= 1; W--) {
		for (auto [i, j]: group[W]) {
			if (top[i][j] + 1 <= top[i][prv[i][j][1]]) {
				dp[top[i][prv[i][j][1]]][j] = max(dp[top[i][prv[i][j][1]]][j], dp[i][j]);
				continue;
			}
			int L = prv[i][j][1] + 1;
			int R = j;
			int T = top[i][j] + 1;
			int B = bottom[i][j] - 1;
			if (top[B + 1][R + 1] + 1 <= T) {
				continue;
			}
			res = max(res, dp[i][j] + (R - L + 1) * (B - T + 1));
			for (int iter = 0; iter < 2; iter++) {
				int row = (iter ? B + 1 : T - 1);
				if (row < 1 || row > N) {
					continue;
				}
				int nxtR = prv[row][R][0];
				while (nxtR >= L) {
					int nxtL = max(L, prv[row][nxtR][1] + 1);
					int nxt_row = (nxtL == L ? i : row); 
					dp[nxt_row][nxtR] = max(dp[nxt_row][nxtR], dp[i][j] + ((R - L + 1) - (nxtR - nxtL + 1)) * (B - T + 1));
					nxtR = prv[row][nxtL - 1][0];
				}
			}
		}
	}
	return res;
}

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8540 KB ok

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8540 KB ok
2 Correct 1 ms 8536 KB ok
3 Correct 1 ms 6648 KB ok
4 Correct 1 ms 8540 KB ok
5 Correct 1 ms 8644 KB ok
6 Correct 1 ms 8540 KB ok
7 Correct 3 ms 15192 KB ok
8 Correct 25 ms 36004 KB ok
9 Correct 396 ms 159568 KB ok

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8540 KB ok
2 Correct 1 ms 8536 KB ok
3 Correct 1 ms 8540 KB ok
4 Correct 1 ms 8540 KB ok
5 Correct 1 ms 8540 KB ok
6 Correct 1 ms 6492 KB ok
7 Correct 1 ms 8536 KB ok
8 Correct 1 ms 8540 KB ok
9 Correct 1 ms 8540 KB ok
10 Correct 1 ms 8536 KB ok
11 Correct 1 ms 8540 KB ok
12 Correct 1 ms 8540 KB ok
13 Correct 1 ms 6492 KB ok

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8540 KB ok
2 Correct 1 ms 8540 KB ok
3 Correct 1 ms 8536 KB ok
4 Correct 1 ms 8540 KB ok
5 Correct 1 ms 8540 KB ok
6 Correct 1 ms 8540 KB ok
7 Correct 1 ms 6492 KB ok
8 Correct 1 ms 8536 KB ok
9 Correct 1 ms 8540 KB ok
10 Correct 1 ms 8540 KB ok
11 Correct 1 ms 8536 KB ok
12 Correct 1 ms 8540 KB ok
13 Correct 1 ms 8540 KB ok
14 Correct 1 ms 6492 KB ok
15 Correct 1 ms 8540 KB ok
16 Correct 1 ms 8540 KB ok
17 Correct 1 ms 8540 KB ok
18 Correct 1 ms 8540 KB ok
19 Correct 1 ms 8540 KB ok
20 Correct 1 ms 6492 KB ok
21 Correct 1 ms 6492 KB ok
22 Correct 1 ms 6492 KB ok
23 Correct 1 ms 6488 KB ok
24 Correct 1 ms 6488 KB ok
25 Correct 1 ms 6492 KB ok
26 Correct 1 ms 8536 KB ok

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8540 KB ok
2 Correct 1 ms 8540 KB ok
3 Correct 1 ms 8536 KB ok
4 Correct 1 ms 6648 KB ok
5 Correct 1 ms 8540 KB ok
6 Correct 1 ms 8540 KB ok
7 Correct 1 ms 8540 KB ok
8 Correct 1 ms 8540 KB ok
9 Correct 1 ms 6492 KB ok
10 Correct 1 ms 8536 KB ok
11 Correct 1 ms 8540 KB ok
12 Correct 1 ms 8540 KB ok
13 Correct 1 ms 8536 KB ok
14 Correct 1 ms 8540 KB ok
15 Correct 1 ms 8540 KB ok
16 Correct 1 ms 6492 KB ok
17 Correct 1 ms 8540 KB ok
18 Correct 1 ms 8540 KB ok
19 Correct 1 ms 8540 KB ok
20 Correct 1 ms 8540 KB ok
21 Correct 1 ms 8540 KB ok
22 Correct 1 ms 6492 KB ok
23 Correct 1 ms 6492 KB ok
24 Correct 1 ms 6492 KB ok
25 Correct 1 ms 6488 KB ok
26 Correct 1 ms 6488 KB ok
27 Correct 1 ms 6492 KB ok
28 Correct 1 ms 8536 KB ok
29 Correct 1 ms 6492 KB ok
30 Correct 1 ms 8792 KB ok
31 Correct 1 ms 8796 KB ok
32 Correct 1 ms 8540 KB ok
33 Correct 1 ms 6748 KB ok
34 Correct 1 ms 6748 KB ok
35 Correct 1 ms 6748 KB ok
36 Correct 1 ms 6748 KB ok
37 Correct 1 ms 6748 KB ok
38 Correct 1 ms 6748 KB ok
39 Correct 1 ms 6748 KB ok
40 Correct 1 ms 8540 KB ok
41 Correct 1 ms 8796 KB ok

Subtask #5
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8540 KB ok
2 Correct 1 ms 8540 KB ok
3 Correct 1 ms 8536 KB ok
4 Correct 1 ms 6648 KB ok
5 Correct 1 ms 8540 KB ok
6 Correct 1 ms 8540 KB ok
7 Correct 1 ms 8540 KB ok
8 Correct 1 ms 8540 KB ok
9 Correct 1 ms 6492 KB ok
10 Correct 1 ms 8536 KB ok
11 Correct 1 ms 8540 KB ok
12 Correct 1 ms 8540 KB ok
13 Correct 1 ms 8536 KB ok
14 Correct 1 ms 8540 KB ok
15 Correct 1 ms 8540 KB ok
16 Correct 1 ms 6492 KB ok
17 Correct 1 ms 8540 KB ok
18 Correct 1 ms 8540 KB ok
19 Correct 1 ms 8540 KB ok
20 Correct 1 ms 8540 KB ok
21 Correct 1 ms 8540 KB ok
22 Correct 1 ms 6492 KB ok
23 Correct 1 ms 6492 KB ok
24 Correct 1 ms 6492 KB ok
25 Correct 1 ms 6488 KB ok
26 Correct 1 ms 6488 KB ok
27 Correct 1 ms 6492 KB ok
28 Correct 1 ms 8536 KB ok
29 Correct 1 ms 6492 KB ok
30 Correct 1 ms 8792 KB ok
31 Correct 1 ms 8796 KB ok
32 Correct 1 ms 8540 KB ok
33 Correct 1 ms 6748 KB ok
34 Correct 1 ms 6748 KB ok
35 Correct 1 ms 6748 KB ok
36 Correct 1 ms 6748 KB ok
37 Correct 1 ms 6748 KB ok
38 Correct 1 ms 6748 KB ok
39 Correct 1 ms 6748 KB ok
40 Correct 1 ms 8540 KB ok
41 Correct 1 ms 8796 KB ok
42 Correct 28 ms 36224 KB ok
43 Correct 29 ms 35904 KB ok
44 Correct 28 ms 36700 KB ok
45 Correct 28 ms 36700 KB ok
46 Correct 34 ms 36504 KB ok
47 Correct 26 ms 36184 KB ok
48 Correct 26 ms 29036 KB ok
49 Correct 24 ms 29192 KB ok
50 Correct 25 ms 30748 KB ok
51 Correct 31 ms 30924 KB ok
52 Correct 22 ms 27228 KB ok
53 Correct 21 ms 26452 KB ok
54 Correct 21 ms 28508 KB ok
55 Correct 22 ms 28252 KB ok
56 Correct 22 ms 30564 KB ok
57 Correct 28 ms 36776 KB ok
58 Correct 32 ms 36844 KB ok
59 Correct 27 ms 36844 KB ok

Subtask #6
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8540 KB ok
2 Correct 1 ms 8540 KB ok
3 Correct 1 ms 8536 KB ok
4 Correct 1 ms 6648 KB ok
5 Correct 1 ms 8540 KB ok
6 Correct 1 ms 8644 KB ok
7 Correct 1 ms 8540 KB ok
8 Correct 3 ms 15192 KB ok
9 Correct 25 ms 36004 KB ok
10 Correct 396 ms 159568 KB ok
11 Correct 1 ms 8540 KB ok
12 Correct 1 ms 8540 KB ok
13 Correct 1 ms 8540 KB ok
14 Correct 1 ms 6492 KB ok
15 Correct 1 ms 8536 KB ok
16 Correct 1 ms 8540 KB ok
17 Correct 1 ms 8540 KB ok
18 Correct 1 ms 8536 KB ok
19 Correct 1 ms 8540 KB ok
20 Correct 1 ms 8540 KB ok
21 Correct 1 ms 6492 KB ok
22 Correct 1 ms 8540 KB ok
23 Correct 1 ms 8540 KB ok
24 Correct 1 ms 8540 KB ok
25 Correct 1 ms 8540 KB ok
26 Correct 1 ms 8540 KB ok
27 Correct 1 ms 6492 KB ok
28 Correct 1 ms 6492 KB ok
29 Correct 1 ms 6492 KB ok
30 Correct 1 ms 6488 KB ok
31 Correct 1 ms 6488 KB ok
32 Correct 1 ms 6492 KB ok
33 Correct 1 ms 8536 KB ok
34 Correct 1 ms 6492 KB ok
35 Correct 1 ms 8792 KB ok
36 Correct 1 ms 8796 KB ok
37 Correct 1 ms 8540 KB ok
38 Correct 1 ms 6748 KB ok
39 Correct 1 ms 6748 KB ok
40 Correct 1 ms 6748 KB ok
41 Correct 1 ms 6748 KB ok
42 Correct 1 ms 6748 KB ok
43 Correct 1 ms 6748 KB ok
44 Correct 1 ms 6748 KB ok
45 Correct 1 ms 8540 KB ok
46 Correct 1 ms 8796 KB ok
47 Correct 28 ms 36224 KB ok
48 Correct 29 ms 35904 KB ok
49 Correct 28 ms 36700 KB ok
50 Correct 28 ms 36700 KB ok
51 Correct 34 ms 36504 KB ok
52 Correct 26 ms 36184 KB ok
53 Correct 26 ms 29036 KB ok
54 Correct 24 ms 29192 KB ok
55 Correct 25 ms 30748 KB ok
56 Correct 31 ms 30924 KB ok
57 Correct 22 ms 27228 KB ok
58 Correct 21 ms 26452 KB ok
59 Correct 21 ms 28508 KB ok
60 Correct 22 ms 28252 KB ok
61 Correct 22 ms 30564 KB ok
62 Correct 28 ms 36776 KB ok
63 Correct 32 ms 36844 KB ok
64 Correct 27 ms 36844 KB ok
65 Correct 523 ms 162596 KB ok
66 Correct 373 ms 138132 KB ok
67 Correct 310 ms 131480 KB ok
68 Correct 414 ms 168232 KB ok
69 Correct 470 ms 163048 KB ok
70 Correct 546 ms 162496 KB ok
71 Correct 414 ms 167716 KB ok
72 Correct 393 ms 159780 KB ok
73 Correct 335 ms 145488 KB ok
74 Correct 352 ms 145156 KB ok
75 Correct 344 ms 146260 KB ok
76 Correct 333 ms 147632 KB ok
77 Correct 336 ms 155568 KB ok
78 Correct 393 ms 173952 KB ok
79 Correct 312 ms 137368 KB ok
80 Correct 305 ms 137080 KB ok
81 Correct 318 ms 139308 KB ok
82 Correct 383 ms 144356 KB ok
83 Correct 356 ms 143544 KB ok
84 Correct 291 ms 127648 KB ok
85 Correct 288 ms 124496 KB ok
86 Correct 314 ms 130312 KB ok
87 Correct 300 ms 131920 KB ok
88 Correct 346 ms 144212 KB ok
89 Correct 402 ms 163956 KB ok
90 Correct 387 ms 155424 KB ok
91 Correct 421 ms 164308 KB ok
92 Correct 333 ms 139576 KB ok
93 Correct 334 ms 139344 KB ok
94 Correct 316 ms 138244 KB ok
95 Correct 308 ms 138096 KB ok
96 Correct 309 ms 137284 KB ok
97 Correct 301 ms 136436 KB ok
98 Correct 286 ms 129304 KB ok
99 Correct 497 ms 169644 KB ok
100 Correct 466 ms 175404 KB ok
101 Correct 481 ms 175780 KB ok
102 Correct 496 ms 175412 KB ok
103 Correct 463 ms 176368 KB ok
104 Correct 513 ms 176376 KB ok
105 Correct 487 ms 175956 KB ok
106 Correct 511 ms 175952 KB ok
107 Correct 467 ms 176620 KB ok
108 Correct 350 ms 168784 KB ok
109 Correct 357 ms 167824 KB ok