Submission #842682

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
842682	2023-09-03T08:38:53 Z	TheLostCookie	Soccer Stadium (IOI23_soccer)	C++17	100 / 100	3496 ms	1448532 KB

soccer

#include "soccer.h"
#include <tuple>

struct SparseTable {
	std::vector<std::vector<int>> t;
	SparseTable(std::vector<int> v) {
		int n = v.size();
		int lg = (n==1?1:(32-__builtin_clz(n-1)));
		t.push_back(v);
		t.resize(lg+1);
		for(int i = 1; i <= lg; i++) {
			t[i].resize(n);
			for(int j = 0; j <= n-(1<<i); j++) {
				t[i][j] = std::max(t[i-1][j],t[i-1][j+(1<<(i-1))]);
			}
		}
	};
	
	//[l,r)
	int query(int l, int r) {
		if(l+1==r) return t[0][l];
		int lg = (31-__builtin_clz(r-l-1));
		return std::max(t[lg][l],t[lg][r-(1<<lg)]);
	}
};

int biggest_stadium(int N, std::vector<std::vector<int>> F) {
	int R = 1;
	while(4*(R+1)*(R+1) <= N) R++;
	
	int ans = 0;
	//Phase 1: Precalculate small segments
	//[x][y][len] = {top,bottom,prec value}
	std::vector<std::vector<std::vector<std::tuple<int,int,int>>>> prec(N,std::vector<std::vector<std::tuple<int,int,int>>>(N,std::vector<std::tuple<int,int,int>>(R+1)));
	for(int y = 0; y < N; y++) {
		for(int x0=0,x1; x0<N; x0=x1+1) {
			x1=x0;
			if(F[x0][y]) prec[x0][y][1] = std::make_tuple(x0,x1,0);
			else {
				while(x1<N-1&&!F[x1+1][y]) x1++;
				for(int i = x0; i <= x1; i++) {
					prec[i][y][1] = std::make_tuple(x0,x1,x1-x0+1);
					ans = std::max(ans,std::get<2>(prec[i][y][1]));
				}
			}
		}
	}
	
	for(int len = 2; len <= R; len++) {
		for(int x = 0; x < N; x++) {
			for(int y = 0; y <= N-len; y++) {
				prec[x][y][len] = std::make_tuple(x,x,0);
				auto [u0,d0,v0] = prec[x][y][len-1];
				auto [u1,d1,v1] = prec[x][y+1][len-1];
				int u = std::max(u0,u1), d = std::min(d0,d1);
				if(v0 && v1) {
					prec[x][y][len] = std::make_tuple(u,d,std::max(v0,v1)+(d-u+1));
					ans = std::max(ans,std::get<2>(prec[x][y][len]));
				}
			}
		}
	}
	
	std::vector<SparseTable> st;
	for(int x = 0; x < N; x++) {
		std::vector<int> v;
		for(int y = 0; y < N; y++) v.push_back(std::get<2>(prec[x][y][R]));
		st.emplace_back(v);
	}
	
	//Phase 2: DP large segments
	//[x] = {left,right,dp value}, filter out all 
	std::vector<std::vector<std::tuple<int,int,int>>> dp(N);
	for(int x = 0; x < N; x++) {
		for(int y0=0,y1; y0 < N; y0=y1+1) {
			y1=y0;
			if(!F[x][y0]) {
				while(y1<N-1&&!F[x][y1+1]) y1++;
				if(y1-y0+1>R) {
					dp[x].emplace_back(y0,y1,y1-y0+1);
					ans = std::max(ans,std::get<2>(dp[x].back())+st[x].query(y0,y1-R+2)-R);
				}
			}
		}
	}
	
	for(int h = 2; h <= N; h++) {
		std::vector<std::vector<std::tuple<int,int,int>>> nxt(N-h+1);
		for(int x=0; x<=N-h; x++) {
			int i0=0,i1=0;
			while(i0<int(dp[x].size())&&i1<int(dp[x+1].size())) {
				auto [l0,r0,v0] = dp[x][i0];
				auto [l1,r1,v1] = dp[x+1][i1];
				if(r0 < l1) i0++;
				else if(r1 < l0) i1++;
				else {
					int l = std::max(l0,l1), r = std::min(r0,r1);
					if(r-l+1 <= R) {
						ans = std::max(ans,std::max(v0,v1)+std::get<2>(prec[x][l][r-l+1])-(h-1)*(r-l+1));
					} else {
						nxt[x].emplace_back(l,r,std::max(v0,v1)+(r-l+1));
						ans = std::max(ans,std::get<2>(nxt[x].back())+st[x].query(l,r-R+2)-h*R);
					}
					
					if(r0<r1) i0++;
					else i1++;
				}
			}
		}
		swap(nxt,dp);
	}
	for(auto [l,r,v]: dp[0]) {
		ans = std::max(ans,v);
	}
	
	return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
6.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	0 ms	344 KB	ok
5	Correct	0 ms	344 KB	ok
6	Correct	0 ms	348 KB	ok
7	Correct	2 ms	1884 KB	ok
8	Correct	99 ms	57252 KB	ok
9	Correct	2785 ms	1442360 KB	ok

Subtask #2
8.0 / 8.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	ok
2	Correct	348 KB	ok
3	Correct	348 KB	ok
4	Correct	348 KB	ok
5	Correct	348 KB	ok
6	Correct	348 KB	ok
7	Correct	348 KB	ok
8	Correct	344 KB	ok
9	Correct	344 KB	ok
10	Correct	348 KB	ok
11	Correct	344 KB	ok
12	Correct	348 KB	ok
13	Correct	348 KB	ok

Subtask #3
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	ok
2	Correct	0 ms	348 KB	ok
3	Correct	0 ms	348 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	348 KB	ok
9	Correct	0 ms	344 KB	ok
10	Correct	0 ms	344 KB	ok
11	Correct	0 ms	348 KB	ok
12	Correct	0 ms	344 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	348 KB	ok
17	Correct	0 ms	348 KB	ok
18	Correct	0 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	348 KB	ok

Subtask #4
18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	ok
2	Correct	0 ms	348 KB	ok
3	Correct	0 ms	348 KB	ok
4	Correct	0 ms	348 KB	ok
5	Correct	0 ms	344 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	348 KB	ok
10	Correct	0 ms	348 KB	ok
11	Correct	0 ms	344 KB	ok
12	Correct	0 ms	344 KB	ok
13	Correct	0 ms	348 KB	ok
14	Correct	0 ms	344 KB	ok
15	Correct	0 ms	348 KB	ok
16	Correct	0 ms	348 KB	ok
17	Correct	0 ms	348 KB	ok
18	Correct	0 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	0 ms	348 KB	ok
27	Correct	0 ms	348 KB	ok
28	Correct	1 ms	348 KB	ok
29	Correct	0 ms	344 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	0 ms	348 KB	ok
34	Correct	0 ms	348 KB	ok
35	Correct	0 ms	348 KB	ok
36	Correct	0 ms	344 KB	ok
37	Correct	0 ms	348 KB	ok
38	Correct	0 ms	348 KB	ok
39	Correct	1 ms	348 KB	ok
40	Correct	0 ms	348 KB	ok
41	Correct	0 ms	348 KB	ok

Subtask #5
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	ok
2	Correct	0 ms	348 KB	ok
3	Correct	0 ms	348 KB	ok
4	Correct	0 ms	348 KB	ok
5	Correct	0 ms	344 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	348 KB	ok
10	Correct	0 ms	348 KB	ok
11	Correct	0 ms	344 KB	ok
12	Correct	0 ms	344 KB	ok
13	Correct	0 ms	348 KB	ok
14	Correct	0 ms	344 KB	ok
15	Correct	0 ms	348 KB	ok
16	Correct	0 ms	348 KB	ok
17	Correct	0 ms	348 KB	ok
18	Correct	0 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	0 ms	348 KB	ok
27	Correct	0 ms	348 KB	ok
28	Correct	1 ms	348 KB	ok
29	Correct	0 ms	344 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	0 ms	348 KB	ok
34	Correct	0 ms	348 KB	ok
35	Correct	0 ms	348 KB	ok
36	Correct	0 ms	344 KB	ok
37	Correct	0 ms	348 KB	ok
38	Correct	0 ms	348 KB	ok
39	Correct	1 ms	348 KB	ok
40	Correct	0 ms	348 KB	ok
41	Correct	0 ms	348 KB	ok
42	Correct	93 ms	57508 KB	ok
43	Correct	94 ms	57488 KB	ok
44	Correct	102 ms	57684 KB	ok
45	Correct	103 ms	57464 KB	ok
46	Correct	103 ms	57668 KB	ok
47	Correct	122 ms	57368 KB	ok
48	Correct	95 ms	57428 KB	ok
49	Correct	95 ms	57476 KB	ok
50	Correct	87 ms	57228 KB	ok
51	Correct	103 ms	57684 KB	ok
52	Correct	85 ms	57472 KB	ok
53	Correct	85 ms	57412 KB	ok
54	Correct	97 ms	57428 KB	ok
55	Correct	89 ms	57232 KB	ok
56	Correct	87 ms	57236 KB	ok
57	Correct	101 ms	57240 KB	ok
58	Correct	104 ms	57480 KB	ok
59	Correct	101 ms	57428 KB	ok

Subtask #6
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	ok
2	Correct	0 ms	348 KB	ok
3	Correct	0 ms	348 KB	ok
4	Correct	0 ms	348 KB	ok
5	Correct	0 ms	344 KB	ok
6	Correct	0 ms	344 KB	ok
7	Correct	0 ms	348 KB	ok
8	Correct	2 ms	1884 KB	ok
9	Correct	99 ms	57252 KB	ok
10	Correct	2785 ms	1442360 KB	ok
11	Correct	0 ms	348 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	344 KB	ok
17	Correct	0 ms	344 KB	ok
18	Correct	0 ms	348 KB	ok
19	Correct	0 ms	344 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	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	348 KB	ok
34	Correct	0 ms	344 KB	ok
35	Correct	0 ms	348 KB	ok
36	Correct	0 ms	348 KB	ok
37	Correct	0 ms	348 KB	ok
38	Correct	0 ms	348 KB	ok
39	Correct	0 ms	348 KB	ok
40	Correct	0 ms	348 KB	ok
41	Correct	0 ms	344 KB	ok
42	Correct	0 ms	348 KB	ok
43	Correct	0 ms	348 KB	ok
44	Correct	1 ms	348 KB	ok
45	Correct	0 ms	348 KB	ok
46	Correct	0 ms	348 KB	ok
47	Correct	93 ms	57508 KB	ok
48	Correct	94 ms	57488 KB	ok
49	Correct	102 ms	57684 KB	ok
50	Correct	103 ms	57464 KB	ok
51	Correct	103 ms	57668 KB	ok
52	Correct	122 ms	57368 KB	ok
53	Correct	95 ms	57428 KB	ok
54	Correct	95 ms	57476 KB	ok
55	Correct	87 ms	57228 KB	ok
56	Correct	103 ms	57684 KB	ok
57	Correct	85 ms	57472 KB	ok
58	Correct	85 ms	57412 KB	ok
59	Correct	97 ms	57428 KB	ok
60	Correct	89 ms	57232 KB	ok
61	Correct	87 ms	57236 KB	ok
62	Correct	101 ms	57240 KB	ok
63	Correct	104 ms	57480 KB	ok
64	Correct	101 ms	57428 KB	ok
65	Correct	2405 ms	1443836 KB	ok
66	Correct	2129 ms	1442944 KB	ok
67	Correct	2053 ms	1443116 KB	ok
68	Correct	2949 ms	1445148 KB	ok
69	Correct	2539 ms	1444908 KB	ok
70	Correct	2475 ms	1444912 KB	ok
71	Correct	3246 ms	1444916 KB	ok
72	Correct	3496 ms	1443956 KB	ok
73	Correct	2443 ms	1443124 KB	ok
74	Correct	2474 ms	1445252 KB	ok
75	Correct	2436 ms	1445728 KB	ok
76	Correct	2244 ms	1445400 KB	ok
77	Correct	2245 ms	1445508 KB	ok
78	Correct	2637 ms	1446156 KB	ok
79	Correct	2051 ms	1445148 KB	ok
80	Correct	2029 ms	1444912 KB	ok
81	Correct	2072 ms	1445536 KB	ok
82	Correct	2155 ms	1445680 KB	ok
83	Correct	2055 ms	1445216 KB	ok
84	Correct	2091 ms	1445168 KB	ok
85	Correct	2067 ms	1445152 KB	ok
86	Correct	2095 ms	1445168 KB	ok
87	Correct	2125 ms	1445176 KB	ok
88	Correct	2316 ms	1445192 KB	ok
89	Correct	2654 ms	1445316 KB	ok
90	Correct	2568 ms	1445164 KB	ok
91	Correct	2597 ms	1445252 KB	ok
92	Correct	2065 ms	1445148 KB	ok
93	Correct	2015 ms	1444908 KB	ok
94	Correct	2045 ms	1444908 KB	ok
95	Correct	2089 ms	1445204 KB	ok
96	Correct	2128 ms	1445168 KB	ok
97	Correct	2103 ms	1445408 KB	ok
98	Correct	2056 ms	1445188 KB	ok
99	Correct	2660 ms	1447700 KB	ok
100	Correct	2690 ms	1445204 KB	ok
101	Correct	2749 ms	1447476 KB	ok
102	Correct	2728 ms	1447720 KB	ok
103	Correct	2735 ms	1447648 KB	ok
104	Correct	2759 ms	1447056 KB	ok
105	Correct	2787 ms	1447984 KB	ok
106	Correct	2831 ms	1448104 KB	ok
107	Correct	2749 ms	1448080 KB	ok
108	Correct	2240 ms	1448500 KB	ok
109	Correct	2244 ms	1448532 KB	ok

Submission #842682

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 16.0 / 16.0

Subtask #6 30.0 / 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
16.0 / 16.0

Subtask #6
30.0 / 30.0