답안 #955211

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
955211	2024-03-29T16:47:37 Z	42kangaroo	축구 경기장 (IOI23_soccer)	C++17	65.5 / 100	329 ms	32080 KB

soccer

#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;
	int su = 0;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			su += F[i][j];
		}
	}
	if (su == 1) {
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				if (F[i][j] == 1) {
					return N*N - min(i + 1, N - i)*min(j + 1, N - j);
				}
			}
		}
	} else {
		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 if (N > 50) return 0;
		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, -N * N))));
			int ma = 0;
			for (int i = N - 1; i >= 0; --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;
		}
	}
}

Compilation message

soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:90:1: warning: control reaches end of non-void function [-Wreturn-type]
   90 | }
      | ^

Subtask #0
0.0 / 0.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	ok

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	ok
2	Correct	0 ms	348 KB	ok
3	Correct	1 ms	348 KB	ok
4	Correct	0 ms	348 KB	ok
5	Correct	0 ms	348 KB	ok
6	Correct	1 ms	344 KB	ok
7	Correct	1 ms	348 KB	ok
8	Correct	15 ms	2396 KB	ok
9	Correct	237 ms	31780 KB	ok

Subtask #2
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	ok
2	Correct	0 ms	348 KB	ok
3	Correct	0 ms	344 KB	ok
4	Correct	0 ms	348 KB	ok
5	Correct	0 ms	348 KB	ok
6	Correct	0 ms	348 KB	ok
7	Correct	0 ms	348 KB	ok
8	Correct	0 ms	600 KB	ok
9	Correct	1 ms	348 KB	ok
10	Correct	0 ms	348 KB	ok
11	Correct	0 ms	348 KB	ok
12	Correct	1 ms	348 KB	ok
13	Correct	0 ms	348 KB	ok

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	ok
2	Correct	0 ms	344 KB	ok
3	Correct	0 ms	348 KB	ok
4	Correct	0 ms	344 KB	ok
5	Correct	0 ms	348 KB	ok
6	Correct	0 ms	348 KB	ok
7	Correct	0 ms	348 KB	ok
8	Correct	0 ms	348 KB	ok
9	Correct	0 ms	600 KB	ok
10	Correct	1 ms	348 KB	ok
11	Correct	0 ms	348 KB	ok
12	Correct	0 ms	348 KB	ok
13	Correct	1 ms	348 KB	ok
14	Correct	0 ms	348 KB	ok
15	Correct	1 ms	544 KB	ok
16	Correct	0 ms	348 KB	ok
17	Correct	0 ms	348 KB	ok
18	Correct	1 ms	348 KB	ok
19	Correct	0 ms	348 KB	ok
20	Correct	0 ms	348 KB	ok
21	Correct	0 ms	348 KB	ok
22	Correct	0 ms	348 KB	ok
23	Correct	0 ms	348 KB	ok
24	Correct	0 ms	348 KB	ok
25	Correct	0 ms	348 KB	ok
26	Correct	1 ms	344 KB	ok

Subtask #4
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	ok
2	Correct	0 ms	344 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	344 KB	ok
7	Correct	0 ms	348 KB	ok
8	Correct	0 ms	348 KB	ok
9	Correct	0 ms	348 KB	ok
10	Correct	0 ms	348 KB	ok
11	Correct	0 ms	600 KB	ok
12	Correct	1 ms	348 KB	ok
13	Correct	0 ms	348 KB	ok
14	Correct	0 ms	348 KB	ok
15	Correct	1 ms	348 KB	ok
16	Correct	0 ms	348 KB	ok
17	Correct	1 ms	544 KB	ok
18	Correct	0 ms	348 KB	ok
19	Correct	0 ms	348 KB	ok
20	Correct	1 ms	348 KB	ok
21	Correct	0 ms	348 KB	ok
22	Correct	0 ms	348 KB	ok
23	Correct	0 ms	348 KB	ok
24	Correct	0 ms	348 KB	ok
25	Correct	0 ms	348 KB	ok
26	Correct	0 ms	348 KB	ok
27	Correct	0 ms	348 KB	ok
28	Correct	1 ms	344 KB	ok
29	Correct	0 ms	348 KB	ok
30	Correct	4 ms	4444 KB	ok
31	Correct	4 ms	4444 KB	ok
32	Correct	4 ms	4444 KB	ok
33	Correct	4 ms	4444 KB	ok
34	Correct	0 ms	348 KB	ok
35	Correct	0 ms	348 KB	ok
36	Correct	4 ms	4444 KB	ok
37	Correct	4 ms	4440 KB	ok
38	Correct	4 ms	4444 KB	ok
39	Correct	4 ms	4444 KB	ok
40	Correct	5 ms	4700 KB	ok
41	Correct	4 ms	4444 KB	ok

Subtask #5
4.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	ok
2	Correct	0 ms	344 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	344 KB	ok
7	Correct	0 ms	348 KB	ok
8	Correct	0 ms	348 KB	ok
9	Correct	0 ms	348 KB	ok
10	Correct	0 ms	348 KB	ok
11	Correct	0 ms	600 KB	ok
12	Correct	1 ms	348 KB	ok
13	Correct	0 ms	348 KB	ok
14	Correct	0 ms	348 KB	ok
15	Correct	1 ms	348 KB	ok
16	Correct	0 ms	348 KB	ok
17	Correct	1 ms	544 KB	ok
18	Correct	0 ms	348 KB	ok
19	Correct	0 ms	348 KB	ok
20	Correct	1 ms	348 KB	ok
21	Correct	0 ms	348 KB	ok
22	Correct	0 ms	348 KB	ok
23	Correct	0 ms	348 KB	ok
24	Correct	0 ms	348 KB	ok
25	Correct	0 ms	348 KB	ok
26	Correct	0 ms	348 KB	ok
27	Correct	0 ms	348 KB	ok
28	Correct	1 ms	344 KB	ok
29	Correct	0 ms	348 KB	ok
30	Correct	4 ms	4444 KB	ok
31	Correct	4 ms	4444 KB	ok
32	Correct	4 ms	4444 KB	ok
33	Correct	4 ms	4444 KB	ok
34	Correct	0 ms	348 KB	ok
35	Correct	0 ms	348 KB	ok
36	Correct	4 ms	4444 KB	ok
37	Correct	4 ms	4440 KB	ok
38	Correct	4 ms	4444 KB	ok
39	Correct	4 ms	4444 KB	ok
40	Correct	5 ms	4700 KB	ok
41	Correct	4 ms	4444 KB	ok
42	Partially correct	15 ms	2392 KB	partial
43	Partially correct	16 ms	2396 KB	partial
44	Partially correct	15 ms	2396 KB	partial
45	Partially correct	15 ms	2396 KB	partial
46	Partially correct	21 ms	2388 KB	partial
47	Partially correct	15 ms	2392 KB	partial
48	Correct	16 ms	2396 KB	ok
49	Partially correct	16 ms	2392 KB	partial
50	Partially correct	16 ms	2200 KB	partial
51	Partially correct	16 ms	2396 KB	partial
52	Partially correct	17 ms	2396 KB	partial
53	Partially correct	21 ms	2388 KB	partial
54	Partially correct	16 ms	2396 KB	partial
55	Partially correct	16 ms	2392 KB	partial
56	Partially correct	17 ms	2396 KB	partial
57	Partially correct	15 ms	2396 KB	partial
58	Partially correct	15 ms	2396 KB	partial
59	Partially correct	15 ms	2392 KB	partial

Subtask #6
7.5 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	ok
2	Correct	0 ms	344 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	Correct	1 ms	344 KB	ok
8	Correct	1 ms	348 KB	ok
9	Correct	15 ms	2396 KB	ok
10	Correct	237 ms	31780 KB	ok
11	Correct	0 ms	344 KB	ok
12	Correct	0 ms	348 KB	ok
13	Correct	0 ms	348 KB	ok
14	Correct	0 ms	348 KB	ok
15	Correct	0 ms	348 KB	ok
16	Correct	0 ms	600 KB	ok
17	Correct	1 ms	348 KB	ok
18	Correct	0 ms	348 KB	ok
19	Correct	0 ms	348 KB	ok
20	Correct	1 ms	348 KB	ok
21	Correct	0 ms	348 KB	ok
22	Correct	1 ms	544 KB	ok
23	Correct	0 ms	348 KB	ok
24	Correct	0 ms	348 KB	ok
25	Correct	1 ms	348 KB	ok
26	Correct	0 ms	348 KB	ok
27	Correct	0 ms	348 KB	ok
28	Correct	0 ms	348 KB	ok
29	Correct	0 ms	348 KB	ok
30	Correct	0 ms	348 KB	ok
31	Correct	0 ms	348 KB	ok
32	Correct	0 ms	348 KB	ok
33	Correct	1 ms	344 KB	ok
34	Correct	0 ms	348 KB	ok
35	Correct	4 ms	4444 KB	ok
36	Correct	4 ms	4444 KB	ok
37	Correct	4 ms	4444 KB	ok
38	Correct	4 ms	4444 KB	ok
39	Correct	0 ms	348 KB	ok
40	Correct	0 ms	348 KB	ok
41	Correct	4 ms	4444 KB	ok
42	Correct	4 ms	4440 KB	ok
43	Correct	4 ms	4444 KB	ok
44	Correct	4 ms	4444 KB	ok
45	Correct	5 ms	4700 KB	ok
46	Correct	4 ms	4444 KB	ok
47	Partially correct	15 ms	2392 KB	partial
48	Partially correct	16 ms	2396 KB	partial
49	Partially correct	15 ms	2396 KB	partial
50	Partially correct	15 ms	2396 KB	partial
51	Partially correct	21 ms	2388 KB	partial
52	Partially correct	15 ms	2392 KB	partial
53	Correct	16 ms	2396 KB	ok
54	Partially correct	16 ms	2392 KB	partial
55	Partially correct	16 ms	2200 KB	partial
56	Partially correct	16 ms	2396 KB	partial
57	Partially correct	17 ms	2396 KB	partial
58	Partially correct	21 ms	2388 KB	partial
59	Partially correct	16 ms	2396 KB	partial
60	Partially correct	16 ms	2392 KB	partial
61	Partially correct	17 ms	2396 KB	partial
62	Partially correct	15 ms	2396 KB	partial
63	Partially correct	15 ms	2396 KB	partial
64	Partially correct	15 ms	2392 KB	partial
65	Partially correct	249 ms	31812 KB	partial
66	Partially correct	274 ms	31824 KB	partial
67	Partially correct	297 ms	31772 KB	partial
68	Partially correct	236 ms	31824 KB	partial
69	Partially correct	238 ms	31832 KB	partial
70	Partially correct	236 ms	31764 KB	partial
71	Partially correct	293 ms	31824 KB	partial
72	Partially correct	230 ms	31780 KB	partial
73	Correct	243 ms	31828 KB	ok
74	Correct	249 ms	31828 KB	ok
75	Partially correct	245 ms	31828 KB	partial
76	Partially correct	249 ms	31764 KB	partial
77	Partially correct	255 ms	31828 KB	partial
78	Partially correct	240 ms	31828 KB	partial
79	Partially correct	260 ms	31772 KB	partial
80	Partially correct	304 ms	31768 KB	partial
81	Partially correct	255 ms	31764 KB	partial
82	Partially correct	248 ms	31760 KB	partial
83	Partially correct	256 ms	31828 KB	partial
84	Partially correct	329 ms	31764 KB	partial
85	Partially correct	257 ms	31776 KB	partial
86	Partially correct	258 ms	31768 KB	partial
87	Partially correct	275 ms	31768 KB	partial
88	Partially correct	248 ms	31764 KB	partial
89	Partially correct	236 ms	31824 KB	partial
90	Partially correct	245 ms	31764 KB	partial
91	Partially correct	237 ms	31768 KB	partial
92	Partially correct	258 ms	31760 KB	partial
93	Partially correct	258 ms	32080 KB	partial
94	Partially correct	252 ms	31828 KB	partial
95	Partially correct	284 ms	31764 KB	partial
96	Partially correct	261 ms	31764 KB	partial
97	Partially correct	292 ms	31768 KB	partial
98	Partially correct	251 ms	31824 KB	partial
99	Partially correct	238 ms	31768 KB	partial
100	Partially correct	241 ms	31764 KB	partial
101	Partially correct	233 ms	31824 KB	partial
102	Partially correct	236 ms	31848 KB	partial
103	Partially correct	236 ms	31768 KB	partial
104	Partially correct	235 ms	31784 KB	partial
105	Partially correct	242 ms	31764 KB	partial
106	Partially correct	232 ms	31760 KB	partial
107	Partially correct	233 ms	31824 KB	partial
108	Partially correct	266 ms	31828 KB	partial
109	Partially correct	268 ms	31824 KB	partial

답안 #955211

Compilation message

Subtask #0 0.0 / 0.0

Subtask #1 6.0 / 6.0

Subtask #2 8.0 / 8.0

Subtask #3 22.0 / 22.0

Subtask #4 18.0 / 18.0

Subtask #5 4.0 / 16.0

Subtask #6 7.5 / 30.0

Subtask #0
0.0 / 0.0

Subtask #1
6.0 / 6.0

Subtask #2
8.0 / 8.0

Subtask #3
22.0 / 22.0

Subtask #4
18.0 / 18.0

Subtask #5
4.0 / 16.0

Subtask #6
7.5 / 30.0