oj.uz

Submission #1068190

# Submission time Handle Problem Language Result Execution time Memory
1068190 2024-08-21T08:23:08 Z AdamGS Soccer Stadium (IOI23_soccer) C++17
100 / 100
 3652 ms 1336308 KB 
#include "soccer.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
#define koduj(x) ((x.st.st)*LIM+x.st.nd)
const ll LIM=2e3+7;
unordered_map<ll,int>mp[LIM][LIM];
vector<int>P[LIM], pole;
vector<pair<int,int>>V[LIM*LIM*2];
int lewo[LIM], prawo[LIM], odw[LIM], lst[LIM], dp[LIM*LIM*2], czy[LIM*LIM*2], ile[LIM], akt, ans;
void DFS(int x) {
	czy[x]=1;
	for(auto i : V[x]) {
		if(!czy[i.st]) DFS(i.st);
		dp[x]=max(dp[x], dp[i.st]+i.nd);
	}
	ans=max(ans, dp[x]+pole[x]);
}
int biggest_stadium(int n, vector<vector<int>>T) {
	pole.pb(0);
	rep(i, n) {
		rep(j, n) {
			++ile[j];
			if(T[i][j]) ile[j]=0;
		}
		rep(j, n+1) {
			P[j].clear();
			lewo[j]=prawo[j]=j;
			odw[j]=0;
			lst[j]=n;
		}
		rep(j, n) P[ile[j]].pb(j);
		for(int j=n; j; --j) for(auto l : P[j]) {
			vector<pair<pair<int,int>,pair<int,int>>>A;
			int a=l, b=l;
			if(l && odw[l-1]) {
				A.pb({{lewo[l-1], l-1}, {i, i-lst[l-1]+1}});
				a=lewo[l-1];
			}
			if(l+1<n && odw[l+1]) {
				A.pb({{l+1, prawo[l+1]}, {i, i-lst[l+1]+1}});
				b=prawo[l+1];
			}
			pair<pair<int,int>,pair<int,int>>x={{a, b}, {i, i-j+1}};
			int k=++akt;
			mp[x.nd.st][x.nd.nd][koduj(x)]=akt;
			pole.pb((x.st.nd-x.st.st+1)*(x.nd.st-x.nd.nd+1));
			for(auto c : A) 
				V[k].pb({mp[c.nd.st][c.nd.nd][koduj(c)], (c.st.nd-c.st.st+1)*(x.nd.nd-c.nd.nd)});	
			if(j>1) {
				--x.nd.st;
				V[mp[x.nd.st][x.nd.nd][koduj(x)]].pb({k, b-a+1});
			}
			odw[l]=1;
			lewo[b]=a;
			prawo[a]=b;
			lst[a]=lst[b]=j;
		}
	}
	rep(i, n) ile[i]=0;
	for(int i=n-1; i>=0; --i) {
		rep(j, n) {
			++ile[j];
			if(T[i][j]) ile[j]=0;
		}
		rep(j, n+1) {
			P[j].clear();
			lewo[j]=prawo[j]=j;
			odw[j]=0;
			lst[j]=n;
		}
		rep(j, n) P[ile[j]].pb(j);
		for(int j=n; j; --j) for(auto l : P[j]) {
			vector<pair<pair<int,int>,pair<int,int>>>A;
			int a=l, b=l;
			if(l && odw[l-1]) {
				A.pb({{lewo[l-1], l-1}, {i+lst[l-1]-1, i}});
				a=lewo[l-1];
			}
			if(l+1<n && odw[l+1]) {
				A.pb({{l+1, prawo[l+1]}, {i+lst[l+1]-1, i}});
				b=prawo[l+1];
			}
			pair<pair<int,int>,pair<int,int>>x={{a, b}, {i+j-1, i}};
			int k=mp[x.nd.st][x.nd.nd][koduj(x)];
			if(!k) {
				mp[x.nd.st][x.nd.nd][koduj(x)]=++akt;
				k=akt;
				pole.pb((x.st.nd-x.st.st+1)*(x.nd.st-x.nd.nd+1));
			}
			for(auto c : A) {
				V[k].pb({mp[c.nd.st][c.nd.nd][koduj(c)], (c.st.nd-c.st.st+1)*(c.nd.st-x.nd.st)});
			}
			odw[l]=1;
			lewo[b]=a;
			prawo[a]=b;
			lst[a]=lst[b]=j;
		}
	}
	rep(i, akt) if(!czy[i+1]) DFS(i+1);
	return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 410196 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 410192 KB ok
2 Correct 156 ms 410192 KB ok
3 Correct 168 ms 410328 KB ok
4 Correct 162 ms 410196 KB ok
5 Correct 167 ms 410172 KB ok
6 Correct 177 ms 410192 KB ok
7 Correct 171 ms 412240 KB ok
8 Correct 275 ms 454852 KB ok
9 Correct 2098 ms 1127104 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 410192 KB ok
2 Correct 156 ms 410192 KB ok
3 Correct 155 ms 410196 KB ok
4 Correct 155 ms 410192 KB ok
5 Correct 162 ms 410196 KB ok
6 Correct 156 ms 410232 KB ok
7 Correct 160 ms 410196 KB ok
8 Correct 165 ms 410192 KB ok
9 Correct 173 ms 410448 KB ok
10 Correct 166 ms 410196 KB ok
11 Correct 164 ms 410192 KB ok
12 Correct 157 ms 410276 KB ok
13 Correct 157 ms 410196 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 410196 KB ok
2 Correct 173 ms 410192 KB ok
3 Correct 156 ms 410192 KB ok
4 Correct 155 ms 410196 KB ok
5 Correct 155 ms 410192 KB ok
6 Correct 162 ms 410196 KB ok
7 Correct 156 ms 410232 KB ok
8 Correct 160 ms 410196 KB ok
9 Correct 165 ms 410192 KB ok
10 Correct 173 ms 410448 KB ok
11 Correct 166 ms 410196 KB ok
12 Correct 164 ms 410192 KB ok
13 Correct 157 ms 410276 KB ok
14 Correct 157 ms 410196 KB ok
15 Correct 156 ms 410172 KB ok
16 Correct 158 ms 410380 KB ok
17 Correct 162 ms 410192 KB ok
18 Correct 172 ms 410196 KB ok
19 Correct 163 ms 410196 KB ok
20 Correct 179 ms 410196 KB ok
21 Correct 161 ms 410196 KB ok
22 Correct 170 ms 410160 KB ok
23 Correct 168 ms 410192 KB ok
24 Correct 169 ms 410196 KB ok
25 Correct 167 ms 410192 KB ok
26 Correct 165 ms 410272 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 410196 KB ok
2 Correct 173 ms 410192 KB ok
3 Correct 156 ms 410192 KB ok
4 Correct 168 ms 410328 KB ok
5 Correct 162 ms 410196 KB ok
6 Correct 155 ms 410196 KB ok
7 Correct 155 ms 410192 KB ok
8 Correct 162 ms 410196 KB ok
9 Correct 156 ms 410232 KB ok
10 Correct 160 ms 410196 KB ok
11 Correct 165 ms 410192 KB ok
12 Correct 173 ms 410448 KB ok
13 Correct 166 ms 410196 KB ok
14 Correct 164 ms 410192 KB ok
15 Correct 157 ms 410276 KB ok
16 Correct 157 ms 410196 KB ok
17 Correct 156 ms 410172 KB ok
18 Correct 158 ms 410380 KB ok
19 Correct 162 ms 410192 KB ok
20 Correct 172 ms 410196 KB ok
21 Correct 163 ms 410196 KB ok
22 Correct 179 ms 410196 KB ok
23 Correct 161 ms 410196 KB ok
24 Correct 170 ms 410160 KB ok
25 Correct 168 ms 410192 KB ok
26 Correct 169 ms 410196 KB ok
27 Correct 167 ms 410192 KB ok
28 Correct 165 ms 410272 KB ok
29 Correct 172 ms 410196 KB ok
30 Correct 163 ms 410448 KB ok
31 Correct 170 ms 410420 KB ok
32 Correct 172 ms 410448 KB ok
33 Correct 155 ms 410276 KB ok
34 Correct 159 ms 410196 KB ok
35 Correct 162 ms 410448 KB ok
36 Correct 162 ms 410196 KB ok
37 Correct 178 ms 410448 KB ok
38 Correct 156 ms 410196 KB ok
39 Correct 156 ms 410364 KB ok
40 Correct 167 ms 410452 KB ok
41 Correct 164 ms 410448 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 410196 KB ok
2 Correct 173 ms 410192 KB ok
3 Correct 156 ms 410192 KB ok
4 Correct 168 ms 410328 KB ok
5 Correct 162 ms 410196 KB ok
6 Correct 155 ms 410196 KB ok
7 Correct 155 ms 410192 KB ok
8 Correct 162 ms 410196 KB ok
9 Correct 156 ms 410232 KB ok
10 Correct 160 ms 410196 KB ok
11 Correct 165 ms 410192 KB ok
12 Correct 173 ms 410448 KB ok
13 Correct 166 ms 410196 KB ok
14 Correct 164 ms 410192 KB ok
15 Correct 157 ms 410276 KB ok
16 Correct 157 ms 410196 KB ok
17 Correct 156 ms 410172 KB ok
18 Correct 158 ms 410380 KB ok
19 Correct 162 ms 410192 KB ok
20 Correct 172 ms 410196 KB ok
21 Correct 163 ms 410196 KB ok
22 Correct 179 ms 410196 KB ok
23 Correct 161 ms 410196 KB ok
24 Correct 170 ms 410160 KB ok
25 Correct 168 ms 410192 KB ok
26 Correct 169 ms 410196 KB ok
27 Correct 167 ms 410192 KB ok
28 Correct 165 ms 410272 KB ok
29 Correct 172 ms 410196 KB ok
30 Correct 163 ms 410448 KB ok
31 Correct 170 ms 410420 KB ok
32 Correct 172 ms 410448 KB ok
33 Correct 155 ms 410276 KB ok
34 Correct 159 ms 410196 KB ok
35 Correct 162 ms 410448 KB ok
36 Correct 162 ms 410196 KB ok
37 Correct 178 ms 410448 KB ok
38 Correct 156 ms 410196 KB ok
39 Correct 156 ms 410364 KB ok
40 Correct 167 ms 410452 KB ok
41 Correct 164 ms 410448 KB ok
42 Correct 315 ms 447984 KB ok
43 Correct 292 ms 441528 KB ok
44 Correct 350 ms 459200 KB ok
45 Correct 413 ms 462272 KB ok
46 Correct 357 ms 452476 KB ok
47 Correct 264 ms 455612 KB ok
48 Correct 267 ms 440264 KB ok
49 Correct 266 ms 441688 KB ok
50 Correct 253 ms 435392 KB ok
51 Correct 287 ms 455240 KB ok
52 Correct 199 ms 421844 KB ok
53 Correct 181 ms 415676 KB ok
54 Correct 197 ms 420812 KB ok
55 Correct 217 ms 426956 KB ok
56 Correct 209 ms 430792 KB ok
57 Correct 306 ms 467388 KB ok
58 Correct 302 ms 466844 KB ok
59 Correct 306 ms 465712 KB ok

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 410196 KB ok
2 Correct 173 ms 410192 KB ok
3 Correct 156 ms 410192 KB ok
4 Correct 168 ms 410328 KB ok
5 Correct 162 ms 410196 KB ok
6 Correct 167 ms 410172 KB ok
7 Correct 177 ms 410192 KB ok
8 Correct 171 ms 412240 KB ok
9 Correct 275 ms 454852 KB ok
10 Correct 2098 ms 1127104 KB ok
11 Correct 155 ms 410196 KB ok
12 Correct 155 ms 410192 KB ok
13 Correct 162 ms 410196 KB ok
14 Correct 156 ms 410232 KB ok
15 Correct 160 ms 410196 KB ok
16 Correct 165 ms 410192 KB ok
17 Correct 173 ms 410448 KB ok
18 Correct 166 ms 410196 KB ok
19 Correct 164 ms 410192 KB ok
20 Correct 157 ms 410276 KB ok
21 Correct 157 ms 410196 KB ok
22 Correct 156 ms 410172 KB ok
23 Correct 158 ms 410380 KB ok
24 Correct 162 ms 410192 KB ok
25 Correct 172 ms 410196 KB ok
26 Correct 163 ms 410196 KB ok
27 Correct 179 ms 410196 KB ok
28 Correct 161 ms 410196 KB ok
29 Correct 170 ms 410160 KB ok
30 Correct 168 ms 410192 KB ok
31 Correct 169 ms 410196 KB ok
32 Correct 167 ms 410192 KB ok
33 Correct 165 ms 410272 KB ok
34 Correct 172 ms 410196 KB ok
35 Correct 163 ms 410448 KB ok
36 Correct 170 ms 410420 KB ok
37 Correct 172 ms 410448 KB ok
38 Correct 155 ms 410276 KB ok
39 Correct 159 ms 410196 KB ok
40 Correct 162 ms 410448 KB ok
41 Correct 162 ms 410196 KB ok
42 Correct 178 ms 410448 KB ok
43 Correct 156 ms 410196 KB ok
44 Correct 156 ms 410364 KB ok
45 Correct 167 ms 410452 KB ok
46 Correct 164 ms 410448 KB ok
47 Correct 315 ms 447984 KB ok
48 Correct 292 ms 441528 KB ok
49 Correct 350 ms 459200 KB ok
50 Correct 413 ms 462272 KB ok
51 Correct 357 ms 452476 KB ok
52 Correct 264 ms 455612 KB ok
53 Correct 267 ms 440264 KB ok
54 Correct 266 ms 441688 KB ok
55 Correct 253 ms 435392 KB ok
56 Correct 287 ms 455240 KB ok
57 Correct 199 ms 421844 KB ok
58 Correct 181 ms 415676 KB ok
59 Correct 197 ms 420812 KB ok
60 Correct 217 ms 426956 KB ok
61 Correct 209 ms 430792 KB ok
62 Correct 306 ms 467388 KB ok
63 Correct 302 ms 466844 KB ok
64 Correct 306 ms 465712 KB ok
65 Correct 2953 ms 1001236 KB ok
66 Correct 812 ms 553608 KB ok
67 Correct 470 ms 467904 KB ok
68 Correct 3601 ms 1252232 KB ok
69 Correct 3384 ms 1139340 KB ok
70 Correct 3652 ms 1104820 KB ok
71 Correct 3475 ms 1268084 KB ok
72 Correct 1782 ms 1143920 KB ok
73 Correct 1742 ms 900500 KB ok
74 Correct 2044 ms 911444 KB ok
75 Correct 1791 ms 905364 KB ok
76 Correct 1305 ms 818316 KB ok
77 Correct 1298 ms 819544 KB ok
78 Correct 2456 ms 1198532 KB ok
79 Correct 496 ms 478140 KB ok
80 Correct 556 ms 481744 KB ok
81 Correct 703 ms 525648 KB ok
82 Correct 1207 ms 621128 KB ok
83 Correct 955 ms 555360 KB ok
84 Correct 634 ms 532148 KB ok
85 Correct 511 ms 497344 KB ok
86 Correct 746 ms 572488 KB ok
87 Correct 801 ms 589444 KB ok
88 Correct 1200 ms 760964 KB ok
89 Correct 1874 ms 1084200 KB ok
90 Correct 1583 ms 949656 KB ok
91 Correct 1888 ms 1035472 KB ok
92 Correct 595 ms 498100 KB ok
93 Correct 548 ms 493656 KB ok
94 Correct 566 ms 481040 KB ok
95 Correct 500 ms 484528 KB ok
96 Correct 569 ms 484824 KB ok
97 Correct 480 ms 485700 KB ok
98 Correct 430 ms 467144 KB ok
99 Correct 2134 ms 1055860 KB ok
100 Correct 2838 ms 1336308 KB ok
101 Correct 2926 ms 1289364 KB ok
102 Correct 3002 ms 1284132 KB ok
103 Correct 2871 ms 1323912 KB ok
104 Correct 2927 ms 1263768 KB ok
105 Correct 3192 ms 1256276 KB ok
106 Correct 2714 ms 1297668 KB ok
107 Correct 2709 ms 1289788 KB ok
108 Correct 1953 ms 1021432 KB ok
109 Correct 2149 ms 1027116 KB ok