oj.uz

Submission #1060258

# Submission time Handle Problem Language Result Execution time Memory
1060258 2024-08-15T12:19:52 Z qilby Soccer Stadium (IOI23_soccer) C++17
100 / 100
 1219 ms 170064 KB 
#include <bits/stdc++.h>

#include "soccer.h"

using namespace std;

const int N = 2009;

map < array < int , 4 > , int > f;
int n, a[N][N], p[N][N], nxt[N][N];

int calc(int li, int ri, int lj, int rj) {
	int l = 1, r = li;

	while (l < r) {
		int mid = (l + r) >> 1;
		if (p[li][rj] - p[li][lj - 1] - p[mid - 1][rj] + p[mid - 1][lj - 1] < 1) r = mid;
		else l = mid + 1;
	}

	if (l < li) return calc(l, ri, lj, rj) + (rj - lj + 1) * (li - l);

	l = ri, r = n;

	while (l < r) {
		int mid = (l + r + 1) >> 1;
		if (p[mid][rj] - p[mid][lj - 1] - p[ri - 1][rj] + p[ri - 1][lj - 1] < 1) l = mid;
		else r = mid - 1;
	}

	if (l > ri) return calc(li, l, lj, rj) + (rj - lj + 1) * (l - ri);

	if (f.count({li, ri, lj, rj})) return f[{li, ri, lj, rj}];

	int crr = 0;

	if (li > 1) {
		for (int j = lj - 1; j < rj; j = nxt[li - 1][j + 1]) {
			if (a[li - 1][j + 1]) continue;
			int l = j + 1, r = min(rj, nxt[li - 1][j + 1] - 1);
			if (l <= r) crr = max(crr, calc(li - 1, ri, l, r) + r - l + 1);
		}
	}

	if (ri < n) {
		for (int j = lj - 1; j < rj; j = nxt[ri + 1][j + 1]) {
			if (a[ri + 1][j + 1]) continue;
			int l = j + 1, r = min(rj, nxt[ri + 1][j + 1] - 1);
			if (l <= r) crr = max(crr, calc(li, ri + 1, l, r) + r - l + 1);
		}
	}

	f[{li, ri, lj, rj}] = crr;

	return crr;
}

int biggest_stadium(int N, vector < vector < int > > w) {
	n = N;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			a[i][j] = w[i - 1][j - 1];
			p[i][j] = p[i][j - 1] + p[i - 1][j] - p[i - 1][j - 1] + a[i][j];
		}
	}

	for (int i = 1; i <= n; i++) {
		nxt[i][n + 1] = n + 1;

		for (int j = n; j >= 1; j--) {
			if (a[i][j]) nxt[i][j] = j;
			else nxt[i][j] = nxt[i][j + 1];
		}
	}

	int res = 0;

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < n; j++) {
			if ((!j || a[i][j]) && !a[i][j + 1]) {
				res = max(res, calc(i, i, j + 1, nxt[i][j + 1] - 1) + nxt[i][j + 1] - j - 1);
			}
		}
	}

	return res;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB ok
2 Correct 0 ms 2396 KB ok
3 Correct 0 ms 2396 KB ok
4 Correct 0 ms 2396 KB ok
5 Correct 0 ms 2396 KB ok
6 Correct 0 ms 2396 KB ok
7 Correct 1 ms 4956 KB ok
8 Correct 27 ms 15700 KB ok
9 Correct 248 ms 79152 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB ok
2 Correct 0 ms 2396 KB ok
3 Correct 1 ms 2392 KB ok
4 Correct 0 ms 2396 KB ok
5 Correct 0 ms 2396 KB ok
6 Correct 0 ms 2396 KB ok
7 Correct 0 ms 2396 KB ok
8 Correct 0 ms 2396 KB ok
9 Correct 0 ms 2396 KB ok
10 Correct 0 ms 2396 KB ok
11 Correct 0 ms 2396 KB ok
12 Correct 1 ms 2392 KB ok
13 Correct 1 ms 2648 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB ok
2 Correct 0 ms 2392 KB ok
3 Correct 0 ms 2396 KB ok
4 Correct 1 ms 2392 KB ok
5 Correct 0 ms 2396 KB ok
6 Correct 0 ms 2396 KB ok
7 Correct 0 ms 2396 KB ok
8 Correct 0 ms 2396 KB ok
9 Correct 0 ms 2396 KB ok
10 Correct 0 ms 2396 KB ok
11 Correct 0 ms 2396 KB ok
12 Correct 0 ms 2396 KB ok
13 Correct 1 ms 2392 KB ok
14 Correct 1 ms 2648 KB ok
15 Correct 1 ms 2396 KB ok
16 Correct 0 ms 2396 KB ok
17 Correct 0 ms 2396 KB ok
18 Correct 0 ms 2396 KB ok
19 Correct 0 ms 2396 KB ok
20 Correct 0 ms 2396 KB ok
21 Correct 0 ms 2396 KB ok
22 Correct 0 ms 2396 KB ok
23 Correct 0 ms 2396 KB ok
24 Correct 1 ms 2392 KB ok
25 Correct 1 ms 2648 KB ok
26 Correct 1 ms 2392 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB ok
2 Correct 0 ms 2392 KB ok
3 Correct 0 ms 2396 KB ok
4 Correct 0 ms 2396 KB ok
5 Correct 0 ms 2396 KB ok
6 Correct 1 ms 2392 KB ok
7 Correct 0 ms 2396 KB ok
8 Correct 0 ms 2396 KB ok
9 Correct 0 ms 2396 KB ok
10 Correct 0 ms 2396 KB ok
11 Correct 0 ms 2396 KB ok
12 Correct 0 ms 2396 KB ok
13 Correct 0 ms 2396 KB ok
14 Correct 0 ms 2396 KB ok
15 Correct 1 ms 2392 KB ok
16 Correct 1 ms 2648 KB ok
17 Correct 1 ms 2396 KB ok
18 Correct 0 ms 2396 KB ok
19 Correct 0 ms 2396 KB ok
20 Correct 0 ms 2396 KB ok
21 Correct 0 ms 2396 KB ok
22 Correct 0 ms 2396 KB ok
23 Correct 0 ms 2396 KB ok
24 Correct 0 ms 2396 KB ok
25 Correct 0 ms 2396 KB ok
26 Correct 1 ms 2392 KB ok
27 Correct 1 ms 2648 KB ok
28 Correct 1 ms 2392 KB ok
29 Correct 1 ms 2396 KB ok
30 Correct 1 ms 4536 KB ok
31 Correct 1 ms 4700 KB ok
32 Correct 1 ms 4700 KB ok
33 Correct 1 ms 4700 KB ok
34 Correct 1 ms 4692 KB ok
35 Correct 1 ms 4700 KB ok
36 Correct 1 ms 4696 KB ok
37 Correct 1 ms 4700 KB ok
38 Correct 1 ms 4540 KB ok
39 Correct 1 ms 4700 KB ok
40 Correct 1 ms 4700 KB ok
41 Correct 1 ms 4700 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB ok
2 Correct 0 ms 2392 KB ok
3 Correct 0 ms 2396 KB ok
4 Correct 0 ms 2396 KB ok
5 Correct 0 ms 2396 KB ok
6 Correct 1 ms 2392 KB ok
7 Correct 0 ms 2396 KB ok
8 Correct 0 ms 2396 KB ok
9 Correct 0 ms 2396 KB ok
10 Correct 0 ms 2396 KB ok
11 Correct 0 ms 2396 KB ok
12 Correct 0 ms 2396 KB ok
13 Correct 0 ms 2396 KB ok
14 Correct 0 ms 2396 KB ok
15 Correct 1 ms 2392 KB ok
16 Correct 1 ms 2648 KB ok
17 Correct 1 ms 2396 KB ok
18 Correct 0 ms 2396 KB ok
19 Correct 0 ms 2396 KB ok
20 Correct 0 ms 2396 KB ok
21 Correct 0 ms 2396 KB ok
22 Correct 0 ms 2396 KB ok
23 Correct 0 ms 2396 KB ok
24 Correct 0 ms 2396 KB ok
25 Correct 0 ms 2396 KB ok
26 Correct 1 ms 2392 KB ok
27 Correct 1 ms 2648 KB ok
28 Correct 1 ms 2392 KB ok
29 Correct 1 ms 2396 KB ok
30 Correct 1 ms 4536 KB ok
31 Correct 1 ms 4700 KB ok
32 Correct 1 ms 4700 KB ok
33 Correct 1 ms 4700 KB ok
34 Correct 1 ms 4692 KB ok
35 Correct 1 ms 4700 KB ok
36 Correct 1 ms 4696 KB ok
37 Correct 1 ms 4700 KB ok
38 Correct 1 ms 4540 KB ok
39 Correct 1 ms 4700 KB ok
40 Correct 1 ms 4700 KB ok
41 Correct 1 ms 4700 KB ok
42 Correct 67 ms 19420 KB ok
43 Correct 72 ms 20032 KB ok
44 Correct 33 ms 16988 KB ok
45 Correct 24 ms 16732 KB ok
46 Correct 52 ms 18316 KB ok
47 Correct 15 ms 16220 KB ok
48 Correct 17 ms 16220 KB ok
49 Correct 16 ms 16276 KB ok
50 Correct 36 ms 16220 KB ok
51 Correct 23 ms 17240 KB ok
52 Correct 16 ms 16216 KB ok
53 Correct 15 ms 16312 KB ok
54 Correct 16 ms 16472 KB ok
55 Correct 16 ms 16272 KB ok
56 Correct 15 ms 16220 KB ok
57 Correct 36 ms 20304 KB ok
58 Correct 38 ms 20788 KB ok
59 Correct 42 ms 21332 KB ok

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB ok
2 Correct 0 ms 2392 KB ok
3 Correct 0 ms 2396 KB ok
4 Correct 0 ms 2396 KB ok
5 Correct 0 ms 2396 KB ok
6 Correct 0 ms 2396 KB ok
7 Correct 0 ms 2396 KB ok
8 Correct 1 ms 4956 KB ok
9 Correct 27 ms 15700 KB ok
10 Correct 248 ms 79152 KB ok
11 Correct 1 ms 2392 KB ok
12 Correct 0 ms 2396 KB ok
13 Correct 0 ms 2396 KB ok
14 Correct 0 ms 2396 KB ok
15 Correct 0 ms 2396 KB ok
16 Correct 0 ms 2396 KB ok
17 Correct 0 ms 2396 KB ok
18 Correct 0 ms 2396 KB ok
19 Correct 0 ms 2396 KB ok
20 Correct 1 ms 2392 KB ok
21 Correct 1 ms 2648 KB ok
22 Correct 1 ms 2396 KB ok
23 Correct 0 ms 2396 KB ok
24 Correct 0 ms 2396 KB ok
25 Correct 0 ms 2396 KB ok
26 Correct 0 ms 2396 KB ok
27 Correct 0 ms 2396 KB ok
28 Correct 0 ms 2396 KB ok
29 Correct 0 ms 2396 KB ok
30 Correct 0 ms 2396 KB ok
31 Correct 1 ms 2392 KB ok
32 Correct 1 ms 2648 KB ok
33 Correct 1 ms 2392 KB ok
34 Correct 1 ms 2396 KB ok
35 Correct 1 ms 4536 KB ok
36 Correct 1 ms 4700 KB ok
37 Correct 1 ms 4700 KB ok
38 Correct 1 ms 4700 KB ok
39 Correct 1 ms 4692 KB ok
40 Correct 1 ms 4700 KB ok
41 Correct 1 ms 4696 KB ok
42 Correct 1 ms 4700 KB ok
43 Correct 1 ms 4540 KB ok
44 Correct 1 ms 4700 KB ok
45 Correct 1 ms 4700 KB ok
46 Correct 1 ms 4700 KB ok
47 Correct 67 ms 19420 KB ok
48 Correct 72 ms 20032 KB ok
49 Correct 33 ms 16988 KB ok
50 Correct 24 ms 16732 KB ok
51 Correct 52 ms 18316 KB ok
52 Correct 15 ms 16220 KB ok
53 Correct 17 ms 16220 KB ok
54 Correct 16 ms 16276 KB ok
55 Correct 36 ms 16220 KB ok
56 Correct 23 ms 17240 KB ok
57 Correct 16 ms 16216 KB ok
58 Correct 15 ms 16312 KB ok
59 Correct 16 ms 16472 KB ok
60 Correct 16 ms 16272 KB ok
61 Correct 15 ms 16220 KB ok
62 Correct 36 ms 20304 KB ok
63 Correct 38 ms 20788 KB ok
64 Correct 42 ms 21332 KB ok
65 Correct 1219 ms 136976 KB ok
66 Correct 595 ms 133224 KB ok
67 Correct 327 ms 107092 KB ok
68 Correct 268 ms 88656 KB ok
69 Correct 534 ms 100184 KB ok
70 Correct 729 ms 109908 KB ok
71 Correct 236 ms 87632 KB ok
72 Correct 221 ms 86356 KB ok
73 Correct 219 ms 86216 KB ok
74 Correct 216 ms 86356 KB ok
75 Correct 220 ms 86356 KB ok
76 Correct 664 ms 86356 KB ok
77 Correct 656 ms 86264 KB ok
78 Correct 309 ms 96336 KB ok
79 Correct 269 ms 90448 KB ok
80 Correct 257 ms 89228 KB ok
81 Correct 263 ms 89172 KB ok
82 Correct 297 ms 93008 KB ok
83 Correct 449 ms 105032 KB ok
84 Correct 220 ms 86356 KB ok
85 Correct 214 ms 86344 KB ok
86 Correct 214 ms 86352 KB ok
87 Correct 219 ms 87380 KB ok
88 Correct 208 ms 86352 KB ok
89 Correct 227 ms 86184 KB ok
90 Correct 220 ms 86356 KB ok
91 Correct 228 ms 86412 KB ok
92 Correct 323 ms 97968 KB ok
93 Correct 337 ms 100076 KB ok
94 Correct 268 ms 90704 KB ok
95 Correct 240 ms 88636 KB ok
96 Correct 238 ms 87892 KB ok
97 Correct 225 ms 87380 KB ok
98 Correct 223 ms 86868 KB ok
99 Correct 851 ms 151636 KB ok
100 Correct 614 ms 149304 KB ok
101 Correct 578 ms 143188 KB ok
102 Correct 615 ms 149220 KB ok
103 Correct 691 ms 159916 KB ok
104 Correct 716 ms 163932 KB ok
105 Correct 749 ms 166732 KB ok
106 Correct 751 ms 170064 KB ok
107 Correct 792 ms 169368 KB ok
108 Correct 379 ms 91476 KB ok
109 Correct 376 ms 91220 KB ok