oj.uz

Submission #878866

# Submission time Handle Problem Language Result Execution time Memory
878866 2023-11-25T11:09:31 Z SanguineChameleon Soccer Stadium (IOI23_soccer) C++17
100 / 100
 572 ms 172624 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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8640 KB ok
2 Correct 1 ms 8640 KB ok
3 Correct 1 ms 6492 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 4 ms 15452 KB ok
8 Correct 27 ms 36432 KB ok
9 Correct 475 ms 163948 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8640 KB ok
2 Correct 1 ms 8640 KB ok
3 Correct 1 ms 8536 KB ok
4 Correct 1 ms 8540 KB ok
5 Correct 2 ms 8792 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 8540 KB ok
11 Correct 1 ms 8540 KB ok
12 Correct 2 ms 8540 KB ok
13 Correct 1 ms 6492 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB ok
2 Correct 1 ms 8640 KB ok
3 Correct 1 ms 8640 KB ok
4 Correct 1 ms 8536 KB ok
5 Correct 1 ms 8540 KB ok
6 Correct 2 ms 8792 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 8540 KB ok
12 Correct 1 ms 8540 KB ok
13 Correct 2 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 8628 KB ok
20 Correct 1 ms 6488 KB ok
21 Correct 2 ms 6496 KB ok
22 Correct 1 ms 6492 KB ok
23 Correct 1 ms 6488 KB ok
24 Correct 1 ms 6632 KB ok
25 Correct 1 ms 6492 KB ok
26 Correct 1 ms 8640 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB ok
2 Correct 1 ms 8640 KB ok
3 Correct 1 ms 8640 KB ok
4 Correct 1 ms 6492 KB ok
5 Correct 1 ms 8540 KB ok
6 Correct 1 ms 8536 KB ok
7 Correct 1 ms 8540 KB ok
8 Correct 2 ms 8792 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 8540 KB ok
14 Correct 1 ms 8540 KB ok
15 Correct 2 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 8628 KB ok
22 Correct 1 ms 6488 KB ok
23 Correct 2 ms 6496 KB ok
24 Correct 1 ms 6492 KB ok
25 Correct 1 ms 6488 KB ok
26 Correct 1 ms 6632 KB ok
27 Correct 1 ms 6492 KB ok
28 Correct 1 ms 8640 KB ok
29 Correct 1 ms 6492 KB ok
30 Correct 1 ms 8800 KB ok
31 Correct 2 ms 8796 KB ok
32 Correct 2 ms 8548 KB ok
33 Correct 1 ms 6748 KB ok
34 Correct 2 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 8652 KB ok
41 Correct 1 ms 8796 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB ok
2 Correct 1 ms 8640 KB ok
3 Correct 1 ms 8640 KB ok
4 Correct 1 ms 6492 KB ok
5 Correct 1 ms 8540 KB ok
6 Correct 1 ms 8536 KB ok
7 Correct 1 ms 8540 KB ok
8 Correct 2 ms 8792 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 8540 KB ok
14 Correct 1 ms 8540 KB ok
15 Correct 2 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 8628 KB ok
22 Correct 1 ms 6488 KB ok
23 Correct 2 ms 6496 KB ok
24 Correct 1 ms 6492 KB ok
25 Correct 1 ms 6488 KB ok
26 Correct 1 ms 6632 KB ok
27 Correct 1 ms 6492 KB ok
28 Correct 1 ms 8640 KB ok
29 Correct 1 ms 6492 KB ok
30 Correct 1 ms 8800 KB ok
31 Correct 2 ms 8796 KB ok
32 Correct 2 ms 8548 KB ok
33 Correct 1 ms 6748 KB ok
34 Correct 2 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 8652 KB ok
41 Correct 1 ms 8796 KB ok
42 Correct 28 ms 36588 KB ok
43 Correct 30 ms 36504 KB ok
44 Correct 29 ms 37208 KB ok
45 Correct 33 ms 37208 KB ok
46 Correct 28 ms 36956 KB ok
47 Correct 29 ms 36752 KB ok
48 Correct 25 ms 29784 KB ok
49 Correct 29 ms 29788 KB ok
50 Correct 26 ms 31184 KB ok
51 Correct 26 ms 31480 KB ok
52 Correct 23 ms 27736 KB ok
53 Correct 21 ms 26968 KB ok
54 Correct 22 ms 29008 KB ok
55 Correct 26 ms 28508 KB ok
56 Correct 22 ms 31068 KB ok
57 Correct 28 ms 37200 KB ok
58 Correct 31 ms 37276 KB ok
59 Correct 30 ms 37200 KB ok

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB ok
2 Correct 1 ms 8640 KB ok
3 Correct 1 ms 8640 KB ok
4 Correct 1 ms 6492 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 4 ms 15452 KB ok
9 Correct 27 ms 36432 KB ok
10 Correct 475 ms 163948 KB ok
11 Correct 1 ms 8536 KB ok
12 Correct 1 ms 8540 KB ok
13 Correct 2 ms 8792 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 8540 KB ok
19 Correct 1 ms 8540 KB ok
20 Correct 2 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 8628 KB ok
27 Correct 1 ms 6488 KB ok
28 Correct 2 ms 6496 KB ok
29 Correct 1 ms 6492 KB ok
30 Correct 1 ms 6488 KB ok
31 Correct 1 ms 6632 KB ok
32 Correct 1 ms 6492 KB ok
33 Correct 1 ms 8640 KB ok
34 Correct 1 ms 6492 KB ok
35 Correct 1 ms 8800 KB ok
36 Correct 2 ms 8796 KB ok
37 Correct 2 ms 8548 KB ok
38 Correct 1 ms 6748 KB ok
39 Correct 2 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 8652 KB ok
46 Correct 1 ms 8796 KB ok
47 Correct 28 ms 36588 KB ok
48 Correct 30 ms 36504 KB ok
49 Correct 29 ms 37208 KB ok
50 Correct 33 ms 37208 KB ok
51 Correct 28 ms 36956 KB ok
52 Correct 29 ms 36752 KB ok
53 Correct 25 ms 29784 KB ok
54 Correct 29 ms 29788 KB ok
55 Correct 26 ms 31184 KB ok
56 Correct 26 ms 31480 KB ok
57 Correct 23 ms 27736 KB ok
58 Correct 21 ms 26968 KB ok
59 Correct 22 ms 29008 KB ok
60 Correct 26 ms 28508 KB ok
61 Correct 22 ms 31068 KB ok
62 Correct 28 ms 37200 KB ok
63 Correct 31 ms 37276 KB ok
64 Correct 30 ms 37200 KB ok
65 Correct 559 ms 166388 KB ok
66 Correct 528 ms 142128 KB ok
67 Correct 325 ms 135200 KB ok
68 Correct 459 ms 172404 KB ok
69 Correct 519 ms 167116 KB ok
70 Correct 572 ms 166520 KB ok
71 Correct 504 ms 171988 KB ok
72 Correct 460 ms 163832 KB ok
73 Correct 375 ms 149588 KB ok
74 Correct 368 ms 149288 KB ok
75 Correct 382 ms 150048 KB ok
76 Correct 423 ms 151772 KB ok
77 Correct 406 ms 152028 KB ok
78 Correct 423 ms 170284 KB ok
79 Correct 320 ms 133572 KB ok
80 Correct 318 ms 133220 KB ok
81 Correct 336 ms 135728 KB ok
82 Correct 356 ms 140672 KB ok
83 Correct 367 ms 139700 KB ok
84 Correct 291 ms 124060 KB ok
85 Correct 298 ms 120624 KB ok
86 Correct 293 ms 126500 KB ok
87 Correct 371 ms 128084 KB ok
88 Correct 332 ms 140580 KB ok
89 Correct 447 ms 160436 KB ok
90 Correct 390 ms 151836 KB ok
91 Correct 422 ms 160520 KB ok
92 Correct 357 ms 136012 KB ok
93 Correct 332 ms 135620 KB ok
94 Correct 315 ms 134500 KB ok
95 Correct 309 ms 133988 KB ok
96 Correct 300 ms 133432 KB ok
97 Correct 310 ms 132756 KB ok
98 Correct 288 ms 125500 KB ok
99 Correct 514 ms 164704 KB ok
100 Correct 464 ms 171584 KB ok
101 Correct 463 ms 171944 KB ok
102 Correct 453 ms 171692 KB ok
103 Correct 457 ms 172612 KB ok
104 Correct 471 ms 172444 KB ok
105 Correct 466 ms 172580 KB ok
106 Correct 438 ms 172076 KB ok
107 Correct 434 ms 172624 KB ok
108 Correct 346 ms 163976 KB ok
109 Correct 356 ms 165148 KB ok