oj.uz

Submission #847527

# Submission time Handle Problem Language Result Execution time Memory
847527 2023-09-09T19:26:36 Z rainboy Soccer Stadium (IOI23_soccer) C++17
100 / 100
 341 ms 94736 KB 
/* upsolved using ideas from PurpleCrayon */
#include "soccer.h"
#include <vector>

using namespace std;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;

const int N = 2000;

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int ll[N][N], uu[N][N], dd[N][N], dp[N][N], ii[N];

int biggest_stadium(int n, vvi aa) {
	for (int i = 0; i < n; i++)
		for (int j = 0, l = 0; j < n; j++)
			if (aa[i][j])
				l = j + 1;
			else
				ll[i][j] = l;
	for (int j = 0; j < n; j++)
		ii[j] = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0, u = 0; j < n; j++)
			if (aa[i][j])
				ii[j] = i + 1, u = 0;
			else
				uu[i][j] = u = max(u, ii[j]);
	for (int j = 0; j < n; j++)
		ii[j] = n - 1;
	for (int i = n - 1; i >= 0; i--)
		for (int j = 0, d = n - 1; j < n; j++)
			if (aa[i][j])
				ii[j] = i - 1, d = n - 1;
			else
				dd[i][j] = d = min(d, ii[j]);
	int ans = 0;
	for (int l = n - 1; l >= 0; l--)
		for (int i = 0; i < n; i++)
			if (!aa[i][l] && ll[i][l] == l)
				for (int j = l; j < n && !aa[i][j]; j++) {
					int u = uu[i][j], d = dd[i][j];
					if (j == l)
						dp[i][j] = d - u + 1;
					else {
						dp[i][j] = dp[i][j - 1] + d - u + 1;
						if (u > 0 && !aa[u - 1][j])
							dp[i][j] = max(dp[i][j], dp[u - 1][j] + (d - u + 1) * (ll[u - 1][j] - ll[i][j]));
						if (d + 1 < n && !aa[d + 1][j])
							dp[i][j] = max(dp[i][j], dp[d + 1][j] + (d - u + 1) * (ll[d + 1][j] - ll[i][j]));
					}
					ans = max(ans, dp[i][j]);
				}
	return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB ok
2 Correct 1 ms 6488 KB ok
3 Correct 1 ms 6488 KB ok
4 Correct 1 ms 6488 KB ok
5 Correct 1 ms 6488 KB ok
6 Correct 1 ms 6488 KB ok
7 Correct 2 ms 9048 KB ok
8 Correct 20 ms 25688 KB ok
9 Correct 289 ms 94480 KB ok

Subtask #2
8.0 / 8.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB ok
2 Correct 1 ms 6488 KB ok
3 Correct 1 ms 6488 KB ok
4 Correct 1 ms 6488 KB ok
5 Correct 1 ms 6492 KB ok
6 Correct 1 ms 6492 KB ok
7 Correct 1 ms 6492 KB ok
8 Correct 1 ms 6492 KB ok
9 Correct 1 ms 6488 KB ok
10 Correct 1 ms 6488 KB ok
11 Correct 1 ms 6488 KB ok
12 Correct 1 ms 6492 KB ok
13 Correct 1 ms 6488 KB ok
14 Correct 1 ms 6488 KB ok
15 Correct 1 ms 6488 KB ok
16 Correct 1 ms 6488 KB ok
17 Correct 1 ms 6492 KB ok
18 Correct 1 ms 6488 KB ok
19 Correct 1 ms 6488 KB ok
20 Correct 1 ms 6488 KB ok
21 Correct 1 ms 6488 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 6488 KB ok
26 Correct 1 ms 6744 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB ok
2 Correct 1 ms 6488 KB ok
3 Correct 1 ms 6488 KB ok
4 Correct 1 ms 6488 KB ok
5 Correct 1 ms 6488 KB ok
6 Correct 1 ms 6488 KB ok
7 Correct 1 ms 6492 KB ok
8 Correct 1 ms 6492 KB ok
9 Correct 1 ms 6492 KB ok
10 Correct 1 ms 6492 KB ok
11 Correct 1 ms 6488 KB ok
12 Correct 1 ms 6488 KB ok
13 Correct 1 ms 6488 KB ok
14 Correct 1 ms 6492 KB ok
15 Correct 1 ms 6488 KB ok
16 Correct 1 ms 6488 KB ok
17 Correct 1 ms 6488 KB ok
18 Correct 1 ms 6488 KB ok
19 Correct 1 ms 6492 KB ok
20 Correct 1 ms 6488 KB ok
21 Correct 1 ms 6488 KB ok
22 Correct 1 ms 6488 KB ok
23 Correct 1 ms 6488 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 6488 KB ok
28 Correct 1 ms 6744 KB ok
29 Correct 1 ms 6488 KB ok
30 Correct 1 ms 6488 KB ok
31 Correct 1 ms 6492 KB ok
32 Correct 1 ms 6492 KB ok
33 Correct 2 ms 6488 KB ok
34 Correct 1 ms 6648 KB ok
35 Correct 1 ms 6488 KB ok
36 Correct 1 ms 6488 KB ok
37 Correct 1 ms 6488 KB ok
38 Correct 1 ms 6488 KB ok
39 Correct 1 ms 6744 KB ok
40 Correct 1 ms 6488 KB ok
41 Correct 1 ms 6744 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB ok
2 Correct 1 ms 6488 KB ok
3 Correct 1 ms 6488 KB ok
4 Correct 1 ms 6488 KB ok
5 Correct 1 ms 6488 KB ok
6 Correct 1 ms 6488 KB ok
7 Correct 1 ms 6492 KB ok
8 Correct 1 ms 6492 KB ok
9 Correct 1 ms 6492 KB ok
10 Correct 1 ms 6492 KB ok
11 Correct 1 ms 6488 KB ok
12 Correct 1 ms 6488 KB ok
13 Correct 1 ms 6488 KB ok
14 Correct 1 ms 6492 KB ok
15 Correct 1 ms 6488 KB ok
16 Correct 1 ms 6488 KB ok
17 Correct 1 ms 6488 KB ok
18 Correct 1 ms 6488 KB ok
19 Correct 1 ms 6492 KB ok
20 Correct 1 ms 6488 KB ok
21 Correct 1 ms 6488 KB ok
22 Correct 1 ms 6488 KB ok
23 Correct 1 ms 6488 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 6488 KB ok
28 Correct 1 ms 6744 KB ok
29 Correct 1 ms 6488 KB ok
30 Correct 1 ms 6488 KB ok
31 Correct 1 ms 6492 KB ok
32 Correct 1 ms 6492 KB ok
33 Correct 2 ms 6488 KB ok
34 Correct 1 ms 6648 KB ok
35 Correct 1 ms 6488 KB ok
36 Correct 1 ms 6488 KB ok
37 Correct 1 ms 6488 KB ok
38 Correct 1 ms 6488 KB ok
39 Correct 1 ms 6744 KB ok
40 Correct 1 ms 6488 KB ok
41 Correct 1 ms 6744 KB ok
42 Correct 23 ms 25680 KB ok
43 Correct 24 ms 25688 KB ok
44 Correct 21 ms 25680 KB ok
45 Correct 20 ms 25688 KB ok
46 Correct 21 ms 25692 KB ok
47 Correct 19 ms 25688 KB ok
48 Correct 19 ms 25432 KB ok
49 Correct 19 ms 25380 KB ok
50 Correct 19 ms 25688 KB ok
51 Correct 20 ms 25748 KB ok
52 Correct 17 ms 20824 KB ok
53 Correct 17 ms 16728 KB ok
54 Correct 17 ms 16984 KB ok
55 Correct 20 ms 23384 KB ok
56 Correct 18 ms 17300 KB ok
57 Correct 19 ms 25740 KB ok
58 Correct 20 ms 25688 KB ok
59 Correct 20 ms 25688 KB ok

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB ok
2 Correct 1 ms 6488 KB ok
3 Correct 1 ms 6488 KB ok
4 Correct 1 ms 6488 KB ok
5 Correct 1 ms 6488 KB ok
6 Correct 1 ms 6488 KB ok
7 Correct 1 ms 6488 KB ok
8 Correct 2 ms 9048 KB ok
9 Correct 20 ms 25688 KB ok
10 Correct 289 ms 94480 KB ok
11 Correct 1 ms 6488 KB ok
12 Correct 1 ms 6492 KB ok
13 Correct 1 ms 6492 KB ok
14 Correct 1 ms 6492 KB ok
15 Correct 1 ms 6492 KB ok
16 Correct 1 ms 6488 KB ok
17 Correct 1 ms 6488 KB ok
18 Correct 1 ms 6488 KB ok
19 Correct 1 ms 6492 KB ok
20 Correct 1 ms 6488 KB ok
21 Correct 1 ms 6488 KB ok
22 Correct 1 ms 6488 KB ok
23 Correct 1 ms 6488 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 6488 KB ok
28 Correct 1 ms 6488 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 6488 KB ok
33 Correct 1 ms 6744 KB ok
34 Correct 1 ms 6488 KB ok
35 Correct 1 ms 6488 KB ok
36 Correct 1 ms 6492 KB ok
37 Correct 1 ms 6492 KB ok
38 Correct 2 ms 6488 KB ok
39 Correct 1 ms 6648 KB ok
40 Correct 1 ms 6488 KB ok
41 Correct 1 ms 6488 KB ok
42 Correct 1 ms 6488 KB ok
43 Correct 1 ms 6488 KB ok
44 Correct 1 ms 6744 KB ok
45 Correct 1 ms 6488 KB ok
46 Correct 1 ms 6744 KB ok
47 Correct 23 ms 25680 KB ok
48 Correct 24 ms 25688 KB ok
49 Correct 21 ms 25680 KB ok
50 Correct 20 ms 25688 KB ok
51 Correct 21 ms 25692 KB ok
52 Correct 19 ms 25688 KB ok
53 Correct 19 ms 25432 KB ok
54 Correct 19 ms 25380 KB ok
55 Correct 19 ms 25688 KB ok
56 Correct 20 ms 25748 KB ok
57 Correct 17 ms 20824 KB ok
58 Correct 17 ms 16728 KB ok
59 Correct 17 ms 16984 KB ok
60 Correct 20 ms 23384 KB ok
61 Correct 18 ms 17300 KB ok
62 Correct 19 ms 25740 KB ok
63 Correct 20 ms 25688 KB ok
64 Correct 20 ms 25688 KB ok
65 Correct 341 ms 94288 KB ok
66 Correct 338 ms 94288 KB ok
67 Correct 292 ms 94364 KB ok
68 Correct 299 ms 94288 KB ok
69 Correct 308 ms 94364 KB ok
70 Correct 326 ms 94544 KB ok
71 Correct 303 ms 94736 KB ok
72 Correct 287 ms 94476 KB ok
73 Correct 269 ms 94000 KB ok
74 Correct 285 ms 93892 KB ok
75 Correct 279 ms 94032 KB ok
76 Correct 298 ms 94288 KB ok
77 Correct 288 ms 94480 KB ok
78 Correct 301 ms 94288 KB ok
79 Correct 293 ms 94476 KB ok
80 Correct 274 ms 94484 KB ok
81 Correct 285 ms 94476 KB ok
82 Correct 278 ms 94312 KB ok
83 Correct 306 ms 94480 KB ok
84 Correct 258 ms 60496 KB ok
85 Correct 254 ms 52304 KB ok
86 Correct 255 ms 66568 KB ok
87 Correct 258 ms 69456 KB ok
88 Correct 266 ms 69716 KB ok
89 Correct 297 ms 94288 KB ok
90 Correct 296 ms 94484 KB ok
91 Correct 295 ms 94464 KB ok
92 Correct 294 ms 94288 KB ok
93 Correct 303 ms 94288 KB ok
94 Correct 274 ms 94288 KB ok
95 Correct 273 ms 94288 KB ok
96 Correct 265 ms 94484 KB ok
97 Correct 269 ms 94488 KB ok
98 Correct 271 ms 94228 KB ok
99 Correct 324 ms 94376 KB ok
100 Correct 298 ms 94504 KB ok
101 Correct 301 ms 94480 KB ok
102 Correct 305 ms 94484 KB ok
103 Correct 308 ms 94288 KB ok
104 Correct 291 ms 94248 KB ok
105 Correct 292 ms 94480 KB ok
106 Correct 289 ms 94476 KB ok
107 Correct 310 ms 94484 KB ok
108 Correct 313 ms 94288 KB ok
109 Correct 311 ms 94476 KB ok