oj.uz

Submission #1064060

# Submission time Handle Problem Language Result Execution time Memory
1064060 2024-08-18T08:54:04 Z DorostWef Soccer Stadium (IOI23_soccer) C++17
70 / 100
 2552 ms 820416 KB 
#include "soccer.h"
#include <bits/stdc++.h>

using namespace std;
const int N = 504, INF = -5000000;
vector <int> a[N][N];
int dp[N][N][N];

int biggest_stadium(int N, std::vector<std::vector<int>> F) {
  
	int mx = 0;
	int n = N;
	if (N >= 501) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (F[i][j]) {
					int mx = min ({(i + 1) * (j + 1), (i + 1) * (n - j), (n - i) * (j + 1), (n - i) * (n - j)});
					return n * n - mx;
				}
			}
		}
	}
	for (int l = n - 1; l >= 0; l--) {
		for (int r = l; r < n; r++) {
			if (l != r) {
				a[l][r] = a[l + 1][r];
			}
			for (int j = 0; j < n; j++) {
				if (F[l][j])
					a[l][r].push_back(j);
			}
			a[l][r].push_back(-1);
			a[l][r].push_back(n);
			sort (a[l][r].begin(), a[l][r].end());
			a[l][r].erase (unique (a[l][r].begin(), a[l][r].end()), a[l][r].end());
			for (int k = 0; k < (int)a[l][r].size() - 1; k++) {
				int L = a[l][r][k];
				int R = a[l][r][k + 1];
				int s = R - L - 1;
				if (L != -1) {
					dp[l][r][L] = INF;
				}
				for (int w = L + 1; w < R; w++) {
					int mm = 0;
					if (l != r) {
						mm = max (dp[l + 1][r][w], dp[l][r - 1][w]);
					}
					dp[l][r][w] = s + mm;
					//cout << l << ' ' << r << ' ' << L << ' ' << R << endl;
					mx = max (mx, dp[l][r][w]);
				}
			}
		}
	}
	return mx;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6236 KB ok
2 Correct 3 ms 6236 KB ok
3 Correct 3 ms 6440 KB ok
4 Correct 3 ms 6492 KB ok
5 Correct 2 ms 6236 KB ok
6 Correct 3 ms 6232 KB ok
7 Correct 9 ms 16988 KB ok
8 Correct 250 ms 261864 KB ok
9 Correct 206 ms 37756 KB ok

Subtask #2
8.0 / 8.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6236 KB ok
2 Correct 3 ms 6236 KB ok
3 Correct 3 ms 6236 KB ok
4 Correct 3 ms 6440 KB ok
5 Correct 3 ms 6492 KB ok
6 Correct 4 ms 6236 KB ok
7 Correct 2 ms 6232 KB ok
8 Correct 3 ms 6236 KB ok
9 Correct 2 ms 6236 KB ok
10 Correct 3 ms 6236 KB ok
11 Correct 4 ms 6236 KB ok
12 Correct 5 ms 6308 KB ok
13 Correct 3 ms 6232 KB ok
14 Correct 3 ms 6232 KB ok
15 Correct 3 ms 6236 KB ok
16 Correct 2 ms 6236 KB ok
17 Correct 3 ms 6236 KB ok
18 Correct 2 ms 6232 KB ok
19 Correct 3 ms 6236 KB ok
20 Correct 4 ms 6272 KB ok
21 Correct 3 ms 6232 KB ok
22 Correct 2 ms 6492 KB ok
23 Correct 3 ms 6236 KB ok
24 Correct 3 ms 6236 KB ok
25 Correct 3 ms 6236 KB ok
26 Correct 3 ms 6236 KB ok
27 Correct 2 ms 6236 KB ok
28 Correct 2 ms 6236 KB ok
29 Correct 3 ms 6232 KB ok
30 Correct 3 ms 7512 KB ok
31 Correct 3 ms 7516 KB ok
32 Correct 3 ms 7516 KB ok
33 Correct 5 ms 7512 KB ok
34 Correct 3 ms 7512 KB ok
35 Correct 5 ms 7516 KB ok
36 Correct 3 ms 7516 KB ok
37 Correct 4 ms 7512 KB ok
38 Correct 4 ms 7516 KB ok
39 Correct 3 ms 7516 KB ok
40 Correct 6 ms 7380 KB ok
41 Correct 4 ms 7260 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6236 KB ok
2 Correct 3 ms 6236 KB ok
3 Correct 3 ms 6236 KB ok
4 Correct 3 ms 6440 KB ok
5 Correct 3 ms 6492 KB ok
6 Correct 4 ms 6236 KB ok
7 Correct 2 ms 6232 KB ok
8 Correct 3 ms 6236 KB ok
9 Correct 2 ms 6236 KB ok
10 Correct 3 ms 6236 KB ok
11 Correct 4 ms 6236 KB ok
12 Correct 5 ms 6308 KB ok
13 Correct 3 ms 6232 KB ok
14 Correct 3 ms 6232 KB ok
15 Correct 3 ms 6236 KB ok
16 Correct 2 ms 6236 KB ok
17 Correct 3 ms 6236 KB ok
18 Correct 2 ms 6232 KB ok
19 Correct 3 ms 6236 KB ok
20 Correct 4 ms 6272 KB ok
21 Correct 3 ms 6232 KB ok
22 Correct 2 ms 6492 KB ok
23 Correct 3 ms 6236 KB ok
24 Correct 3 ms 6236 KB ok
25 Correct 3 ms 6236 KB ok
26 Correct 3 ms 6236 KB ok
27 Correct 2 ms 6236 KB ok
28 Correct 2 ms 6236 KB ok
29 Correct 3 ms 6232 KB ok
30 Correct 3 ms 7512 KB ok
31 Correct 3 ms 7516 KB ok
32 Correct 3 ms 7516 KB ok
33 Correct 5 ms 7512 KB ok
34 Correct 3 ms 7512 KB ok
35 Correct 5 ms 7516 KB ok
36 Correct 3 ms 7516 KB ok
37 Correct 4 ms 7512 KB ok
38 Correct 4 ms 7516 KB ok
39 Correct 3 ms 7516 KB ok
40 Correct 6 ms 7380 KB ok
41 Correct 4 ms 7260 KB ok
42 Correct 1122 ms 733404 KB ok
43 Correct 1419 ms 743096 KB ok
44 Correct 760 ms 597000 KB ok
45 Correct 546 ms 502984 KB ok
46 Correct 983 ms 710176 KB ok
47 Correct 226 ms 266320 KB ok
48 Correct 1502 ms 686960 KB ok
49 Correct 1393 ms 650852 KB ok
50 Correct 981 ms 506452 KB ok
51 Correct 1041 ms 683088 KB ok
52 Correct 2448 ms 820416 KB ok
53 Correct 2552 ms 779980 KB ok
54 Correct 2187 ms 776700 KB ok
55 Correct 2290 ms 790048 KB ok
56 Correct 1303 ms 669488 KB ok
57 Correct 434 ms 424784 KB ok
58 Correct 453 ms 443984 KB ok
59 Correct 665 ms 472404 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6236 KB ok
2 Correct 3 ms 6236 KB ok
3 Correct 3 ms 6236 KB ok
4 Correct 3 ms 6440 KB ok
5 Correct 3 ms 6492 KB ok
6 Correct 2 ms 6236 KB ok
7 Correct 3 ms 6232 KB ok
8 Correct 9 ms 16988 KB ok
9 Correct 250 ms 261864 KB ok
10 Correct 206 ms 37756 KB ok
11 Correct 4 ms 6236 KB ok
12 Correct 2 ms 6232 KB ok
13 Correct 3 ms 6236 KB ok
14 Correct 2 ms 6236 KB ok
15 Correct 3 ms 6236 KB ok
16 Correct 4 ms 6236 KB ok
17 Correct 5 ms 6308 KB ok
18 Correct 3 ms 6232 KB ok
19 Correct 3 ms 6232 KB ok
20 Correct 3 ms 6236 KB ok
21 Correct 2 ms 6236 KB ok
22 Correct 3 ms 6236 KB ok
23 Correct 2 ms 6232 KB ok
24 Correct 3 ms 6236 KB ok
25 Correct 4 ms 6272 KB ok
26 Correct 3 ms 6232 KB ok
27 Correct 2 ms 6492 KB ok
28 Correct 3 ms 6236 KB ok
29 Correct 3 ms 6236 KB ok
30 Correct 3 ms 6236 KB ok
31 Correct 3 ms 6236 KB ok
32 Correct 2 ms 6236 KB ok
33 Correct 2 ms 6236 KB ok
34 Correct 3 ms 6232 KB ok
35 Correct 3 ms 7512 KB ok
36 Correct 3 ms 7516 KB ok
37 Correct 3 ms 7516 KB ok
38 Correct 5 ms 7512 KB ok
39 Correct 3 ms 7512 KB ok
40 Correct 5 ms 7516 KB ok
41 Correct 3 ms 7516 KB ok
42 Correct 4 ms 7512 KB ok
43 Correct 4 ms 7516 KB ok
44 Correct 3 ms 7516 KB ok
45 Correct 6 ms 7380 KB ok
46 Correct 4 ms 7260 KB ok
47 Correct 1122 ms 733404 KB ok
48 Correct 1419 ms 743096 KB ok
49 Correct 760 ms 597000 KB ok
50 Correct 546 ms 502984 KB ok
51 Correct 983 ms 710176 KB ok
52 Correct 226 ms 266320 KB ok
53 Correct 1502 ms 686960 KB ok
54 Correct 1393 ms 650852 KB ok
55 Correct 981 ms 506452 KB ok
56 Correct 1041 ms 683088 KB ok
57 Correct 2448 ms 820416 KB ok
58 Correct 2552 ms 779980 KB ok
59 Correct 2187 ms 776700 KB ok
60 Correct 2290 ms 790048 KB ok
61 Correct 1303 ms 669488 KB ok
62 Correct 434 ms 424784 KB ok
63 Correct 453 ms 443984 KB ok
64 Correct 665 ms 472404 KB ok
65 Partially correct 192 ms 45652 KB partial
66 Partially correct 201 ms 45672 KB partial
67 Partially correct 199 ms 45672 KB partial
68 Partially correct 207 ms 45676 KB partial
69 Partially correct 195 ms 45652 KB partial
70 Partially correct 198 ms 45652 KB partial
71 Partially correct 188 ms 45648 KB partial
72 Partially correct 187 ms 45652 KB partial
73 Incorrect 192 ms 45648 KB wrong
74 Halted 0 ms 0 KB -