oj.uz

Submission #1065249

# Submission time Handle Problem Language Result Execution time Memory
1065249 2024-08-19T04:29:41 Z Gromp15 Soccer Stadium (IOI23_soccer) C++17
18 / 100
 4500 ms 1011800 KB 
#include <bits/stdc++.h>
#include "soccer.h"
#define ar array
#define ll long long
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

const int nax = 505;
int dp[nax][nax][nax][2];
int biggest_stadium(int n, std::vector<std::vector<int>> F)
{
	memset(dp, 0xc0, sizeof(dp));
	vector<vector<int>> to(n, vector<int>(n, -1));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) if (!F[i][j]) {
			int r = j;
			while (r+1 < n && !F[i][r+1]) r++;
			for (int k = j; k <= r; k++) to[i][k] = r;
			dp[i][i][j][0] = r-j+1;
			j = r;
		}
	}
	for (int len = 1; len < n; len++) {
		for (int i = 0; i+len-1 < n; i++) {
			int j = i+len-1;
			for (int l = 0; l < n; l++) {
				for (int k = 0; k < 2; k++) if (dp[i][j][l][k] > 0) {
					int r = k ? to[j][l] : to[i][l];
					if (i) {
						for (int z = l; z <= r; z++) if (~to[i-1][z]) {
							if (to[i-1][z] <= r) {
								ckmax(dp[i-1][j][z][0], dp[i][j][l][k] + to[i-1][z] - z + 1);
							}
							else {
								ckmax(dp[i-1][j][z][k], dp[i][j][l][k] + r - z + 1);
							}
						}
					}
					if (j+1 < n) {
						for (int z = l; z <= r; z++) if (~to[j+1][z]) {
							if (to[j+1][z] <= r) {
								ckmax(dp[i][j+1][z][1], dp[i][j][l][k] + to[j+1][z] - z + 1);
							}
							else {
								ckmax(dp[i][j+1][z][k], dp[i][j][l][k] + r - z + 1);
							}
						}
					}
				}
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++) for (int j = i; j < n; j++) for (int k = 0; k < n; k++) for (int l = 0; l < 2; l++) ckmax(ans, dp[i][j][k][l]);
	return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 1008464 KB ok
2 Correct 407 ms 1008464 KB ok
3 Correct 432 ms 1008472 KB ok
4 Correct 427 ms 1008332 KB ok
5 Correct 421 ms 1008468 KB ok
6 Correct 418 ms 1008468 KB ok
7 Partially correct 567 ms 1008476 KB partial
8 Execution timed out 4603 ms 1011800 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 1008464 KB ok
2 Correct 407 ms 1008464 KB ok
3 Correct 437 ms 1008468 KB ok
4 Correct 422 ms 1008420 KB ok
5 Correct 423 ms 1008364 KB ok
6 Correct 432 ms 1008464 KB ok
7 Correct 433 ms 1008380 KB ok
8 Correct 423 ms 1008344 KB ok
9 Correct 438 ms 1008456 KB ok
10 Correct 443 ms 1008608 KB ok
11 Correct 424 ms 1008488 KB ok
12 Correct 421 ms 1008464 KB ok
13 Correct 414 ms 1008468 KB ok

Subtask #3
5.5 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 424 ms 1008464 KB ok
2 Correct 426 ms 1008464 KB ok
3 Correct 407 ms 1008464 KB ok
4 Correct 437 ms 1008468 KB ok
5 Correct 422 ms 1008420 KB ok
6 Correct 423 ms 1008364 KB ok
7 Correct 432 ms 1008464 KB ok
8 Correct 433 ms 1008380 KB ok
9 Correct 423 ms 1008344 KB ok
10 Correct 438 ms 1008456 KB ok
11 Correct 443 ms 1008608 KB ok
12 Correct 424 ms 1008488 KB ok
13 Correct 421 ms 1008464 KB ok
14 Correct 414 ms 1008468 KB ok
15 Correct 409 ms 1008312 KB ok
16 Partially correct 445 ms 1008460 KB partial
17 Partially correct 409 ms 1008356 KB partial
18 Partially correct 424 ms 1008520 KB partial
19 Correct 438 ms 1008424 KB ok
20 Correct 429 ms 1008540 KB ok
21 Correct 428 ms 1008480 KB ok
22 Correct 425 ms 1008464 KB ok
23 Correct 432 ms 1008324 KB ok
24 Correct 416 ms 1008468 KB ok
25 Correct 434 ms 1008464 KB ok
26 Correct 435 ms 1008392 KB ok

Subtask #4
4.5 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 424 ms 1008464 KB ok
2 Correct 426 ms 1008464 KB ok
3 Correct 407 ms 1008464 KB ok
4 Correct 432 ms 1008472 KB ok
5 Correct 427 ms 1008332 KB ok
6 Correct 437 ms 1008468 KB ok
7 Correct 422 ms 1008420 KB ok
8 Correct 423 ms 1008364 KB ok
9 Correct 432 ms 1008464 KB ok
10 Correct 433 ms 1008380 KB ok
11 Correct 423 ms 1008344 KB ok
12 Correct 438 ms 1008456 KB ok
13 Correct 443 ms 1008608 KB ok
14 Correct 424 ms 1008488 KB ok
15 Correct 421 ms 1008464 KB ok
16 Correct 414 ms 1008468 KB ok
17 Correct 409 ms 1008312 KB ok
18 Partially correct 445 ms 1008460 KB partial
19 Partially correct 409 ms 1008356 KB partial
20 Partially correct 424 ms 1008520 KB partial
21 Correct 438 ms 1008424 KB ok
22 Correct 429 ms 1008540 KB ok
23 Correct 428 ms 1008480 KB ok
24 Correct 425 ms 1008464 KB ok
25 Correct 432 ms 1008324 KB ok
26 Correct 416 ms 1008468 KB ok
27 Correct 434 ms 1008464 KB ok
28 Correct 435 ms 1008392 KB ok
29 Correct 434 ms 1008320 KB ok
30 Partially correct 421 ms 1008528 KB partial
31 Partially correct 420 ms 1008468 KB partial
32 Partially correct 449 ms 1008460 KB partial
33 Correct 435 ms 1008468 KB ok
34 Correct 414 ms 1008408 KB ok
35 Correct 445 ms 1008724 KB ok
36 Correct 423 ms 1008396 KB ok
37 Correct 450 ms 1008464 KB ok
38 Correct 428 ms 1008468 KB ok
39 Correct 440 ms 1008464 KB ok
40 Correct 430 ms 1008468 KB ok
41 Correct 438 ms 1008468 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 424 ms 1008464 KB ok
2 Correct 426 ms 1008464 KB ok
3 Correct 407 ms 1008464 KB ok
4 Correct 432 ms 1008472 KB ok
5 Correct 427 ms 1008332 KB ok
6 Correct 437 ms 1008468 KB ok
7 Correct 422 ms 1008420 KB ok
8 Correct 423 ms 1008364 KB ok
9 Correct 432 ms 1008464 KB ok
10 Correct 433 ms 1008380 KB ok
11 Correct 423 ms 1008344 KB ok
12 Correct 438 ms 1008456 KB ok
13 Correct 443 ms 1008608 KB ok
14 Correct 424 ms 1008488 KB ok
15 Correct 421 ms 1008464 KB ok
16 Correct 414 ms 1008468 KB ok
17 Correct 409 ms 1008312 KB ok
18 Partially correct 445 ms 1008460 KB partial
19 Partially correct 409 ms 1008356 KB partial
20 Partially correct 424 ms 1008520 KB partial
21 Correct 438 ms 1008424 KB ok
22 Correct 429 ms 1008540 KB ok
23 Correct 428 ms 1008480 KB ok
24 Correct 425 ms 1008464 KB ok
25 Correct 432 ms 1008324 KB ok
26 Correct 416 ms 1008468 KB ok
27 Correct 434 ms 1008464 KB ok
28 Correct 435 ms 1008392 KB ok
29 Correct 434 ms 1008320 KB ok
30 Partially correct 421 ms 1008528 KB partial
31 Partially correct 420 ms 1008468 KB partial
32 Partially correct 449 ms 1008460 KB partial
33 Correct 435 ms 1008468 KB ok
34 Correct 414 ms 1008408 KB ok
35 Correct 445 ms 1008724 KB ok
36 Correct 423 ms 1008396 KB ok
37 Correct 450 ms 1008464 KB ok
38 Correct 428 ms 1008468 KB ok
39 Correct 440 ms 1008464 KB ok
40 Correct 430 ms 1008468 KB ok
41 Correct 438 ms 1008468 KB ok
42 Execution timed out 4601 ms 1011284 KB Time limit exceeded
43 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 424 ms 1008464 KB ok
2 Correct 426 ms 1008464 KB ok
3 Correct 407 ms 1008464 KB ok
4 Correct 432 ms 1008472 KB ok
5 Correct 427 ms 1008332 KB ok
6 Correct 421 ms 1008468 KB ok
7 Correct 418 ms 1008468 KB ok
8 Partially correct 567 ms 1008476 KB partial
9 Execution timed out 4603 ms 1011800 KB Time limit exceeded
10 Halted 0 ms 0 KB -