oj.uz

Submission #955202

# Submission time Handle Problem Language Result Execution time Memory
955202 2024-03-29T16:33:16 Z 42kangaroo Soccer Stadium (IOI23_soccer) C++17
12 / 100
 3602 ms 2097152 KB 
#include "soccer.h"
#include "bits/stdc++.h"


int biggest_stadium(int N, std::vector<std::vector<int>> F) {
	using namespace std;
	using dp_t = vector<vector<vector<vector<int>>>>;
	bool allPos = true;
	vector<pair<int, int>> ra(N);
	vector<int> les(N);
	for (int i = 0; i < N; ++i) {
		ra[i].first = 0;
		for (; ra[i].first < N; ra[i].first++) {
			if (F[i][ra[i].first] == 0) break;
		}
		ra[i].second = N - 1;
		for (; ra[i].second >= 0; ra[i].second--) {
			if (F[i][ra[i].second] == 0) break;
		}
		les[i] = ra[i].second - ra[i].first + 1;
		for (int j = ra[i].first; j <= ra[i].second; ++j) {
			if (F[i][j] == 1) allPos = false;
		}
		if (!allPos) break;
	}
	int tot = 0;
	int maI = max_element(les.begin(), les.end()) - les.begin();
	pair<int,int> actRa = ra[maI];
	pair<int,int> oRa = {maI, maI};
	tot = les[maI];
	while (allPos && oRa != make_pair(0, N - 1)) {
		int ne = oRa.first -1;
		if (ne < 0 || (oRa.second < N - 1 && les[ne] < les[oRa.second + 1])) ne = oRa.second + 1;
		if (les[ne] < 0) break;
		if (actRa.first > ra[ne].first || actRa.second < ra[ne].second) allPos = false;
		actRa = ra[ne];
		tot += les[ne];
		oRa = {min(oRa.first, ne), max(oRa.second, ne)};
	}
	if (allPos) return tot;
	else {
		vector<vector<int>> prefS(N, vector<int>(N + 1, 0));
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				prefS[i][j + 1] = prefS[i][j] + F[i][j];
			}
		}
		dp_t dp(N, vector<vector<vector<int>>>(N, vector<vector<int>>(N, vector<int>(N, -1))));
		int ma = 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 = N - 1; l >= k; --l) {
						if (l < N - 1) dp[i][j][k][l] = dp[i][j][k][l + 1];
						if (k > 0) dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k - 1][l]);
						if (i == j) {
							if (prefS[i][l + 1] - prefS[i][k] == 0) dp[i][j][k][l] = max(dp[i][j][k][l], l - k + 1);
						} else {
							if (prefS[i][l + 1] - prefS[i][k] == 0) dp[i][j][k][l] = max(dp[i][j][k][l], l - k + 1 + dp[i + 1][j][k][l]);
							if (prefS[j][l + 1] - prefS[j][k] == 0) dp[i][j][k][l] = max(dp[i][j][k][l], l - k + 1+ dp[i][j - 1][k][l]);
						}
						ma = max(ma, dp[i][j][k][l]);
					}
				}
			}
		}
		return ma;
	}
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB partial

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Partially correct 527 ms 436036 KB partial
8 Runtime error 3602 ms 2097152 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #2
2.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 352 KB ok
4 Correct 1 ms 352 KB ok
5 Partially correct 0 ms 352 KB partial
6 Correct 1 ms 356 KB ok
7 Partially correct 0 ms 356 KB partial
8 Correct 1 ms 352 KB ok
9 Correct 0 ms 356 KB ok
10 Correct 0 ms 356 KB ok
11 Correct 0 ms 352 KB ok
12 Correct 1 ms 360 KB ok
13 Correct 1 ms 360 KB ok

Subtask #3
5.5 / 22.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB partial
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 352 KB ok
5 Correct 1 ms 352 KB ok
6 Partially correct 0 ms 352 KB partial
7 Correct 1 ms 356 KB ok
8 Partially correct 0 ms 356 KB partial
9 Correct 1 ms 352 KB ok
10 Correct 0 ms 356 KB ok
11 Correct 0 ms 356 KB ok
12 Correct 0 ms 352 KB ok
13 Correct 1 ms 360 KB ok
14 Correct 1 ms 360 KB ok
15 Correct 1 ms 360 KB ok
16 Correct 0 ms 360 KB ok
17 Partially correct 0 ms 356 KB partial
18 Partially correct 0 ms 360 KB partial
19 Partially correct 0 ms 360 KB partial
20 Correct 1 ms 360 KB ok
21 Correct 0 ms 360 KB ok
22 Partially correct 1 ms 360 KB partial
23 Partially correct 1 ms 360 KB partial
24 Partially correct 1 ms 444 KB partial
25 Partially correct 1 ms 612 KB partial
26 Partially correct 1 ms 360 KB partial

Subtask #4
4.5 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB partial
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 0 ms 352 KB ok
7 Correct 1 ms 352 KB ok
8 Partially correct 0 ms 352 KB partial
9 Correct 1 ms 356 KB ok
10 Partially correct 0 ms 356 KB partial
11 Correct 1 ms 352 KB ok
12 Correct 0 ms 356 KB ok
13 Correct 0 ms 356 KB ok
14 Correct 0 ms 352 KB ok
15 Correct 1 ms 360 KB ok
16 Correct 1 ms 360 KB ok
17 Correct 1 ms 360 KB ok
18 Correct 0 ms 360 KB ok
19 Partially correct 0 ms 356 KB partial
20 Partially correct 0 ms 360 KB partial
21 Partially correct 0 ms 360 KB partial
22 Correct 1 ms 360 KB ok
23 Correct 0 ms 360 KB ok
24 Partially correct 1 ms 360 KB partial
25 Partially correct 1 ms 360 KB partial
26 Partially correct 1 ms 444 KB partial
27 Partially correct 1 ms 612 KB partial
28 Partially correct 1 ms 360 KB partial
29 Partially correct 1 ms 360 KB partial
30 Partially correct 5 ms 4452 KB partial
31 Partially correct 4 ms 4460 KB partial
32 Partially correct 4 ms 4444 KB partial
33 Partially correct 4 ms 4440 KB partial
34 Correct 0 ms 348 KB ok
35 Correct 0 ms 444 KB ok
36 Partially correct 6 ms 4440 KB partial
37 Partially correct 4 ms 4448 KB partial
38 Partially correct 4 ms 4444 KB partial
39 Partially correct 4 ms 4604 KB partial
40 Correct 4 ms 4440 KB ok
41 Partially correct 4 ms 4440 KB partial

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB partial
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 0 ms 352 KB ok
7 Correct 1 ms 352 KB ok
8 Partially correct 0 ms 352 KB partial
9 Correct 1 ms 356 KB ok
10 Partially correct 0 ms 356 KB partial
11 Correct 1 ms 352 KB ok
12 Correct 0 ms 356 KB ok
13 Correct 0 ms 356 KB ok
14 Correct 0 ms 352 KB ok
15 Correct 1 ms 360 KB ok
16 Correct 1 ms 360 KB ok
17 Correct 1 ms 360 KB ok
18 Correct 0 ms 360 KB ok
19 Partially correct 0 ms 356 KB partial
20 Partially correct 0 ms 360 KB partial
21 Partially correct 0 ms 360 KB partial
22 Correct 1 ms 360 KB ok
23 Correct 0 ms 360 KB ok
24 Partially correct 1 ms 360 KB partial
25 Partially correct 1 ms 360 KB partial
26 Partially correct 1 ms 444 KB partial
27 Partially correct 1 ms 612 KB partial
28 Partially correct 1 ms 360 KB partial
29 Partially correct 1 ms 360 KB partial
30 Partially correct 5 ms 4452 KB partial
31 Partially correct 4 ms 4460 KB partial
32 Partially correct 4 ms 4444 KB partial
33 Partially correct 4 ms 4440 KB partial
34 Correct 0 ms 348 KB ok
35 Correct 0 ms 444 KB ok
36 Partially correct 6 ms 4440 KB partial
37 Partially correct 4 ms 4448 KB partial
38 Partially correct 4 ms 4444 KB partial
39 Partially correct 4 ms 4604 KB partial
40 Correct 4 ms 4440 KB ok
41 Partially correct 4 ms 4440 KB partial
42 Runtime error 3449 ms 2097152 KB Execution killed with signal 9
43 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB partial
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Partially correct 527 ms 436036 KB partial
9 Runtime error 3602 ms 2097152 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -