oj.uz

Submission #1068185

# Submission time Handle Problem Language Result Execution time Memory
1068185 2024-08-21T08:21:07 Z AdamGS Soccer Stadium (IOI23_soccer) C++17
70 / 100
 4500 ms 923748 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)*LIM)+x.nd.st)
const ll LIM=2e3+7;
unordered_map<ll,int>mp[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.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.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.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.nd][koduj(x)];
			if(!k) {
				mp[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.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 83 ms 191060 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 191120 KB ok
2 Correct 79 ms 191076 KB ok
3 Correct 79 ms 191056 KB ok
4 Correct 84 ms 191348 KB ok
5 Correct 82 ms 191032 KB ok
6 Correct 73 ms 191060 KB ok
7 Correct 100 ms 192812 KB ok
8 Correct 193 ms 236448 KB ok
9 Correct 1824 ms 923748 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 191120 KB ok
2 Correct 79 ms 191076 KB ok
3 Correct 72 ms 191060 KB ok
4 Correct 78 ms 190964 KB ok
5 Correct 76 ms 191056 KB ok
6 Correct 81 ms 191056 KB ok
7 Correct 83 ms 191120 KB ok
8 Correct 98 ms 191056 KB ok
9 Correct 92 ms 191056 KB ok
10 Correct 78 ms 190988 KB ok
11 Correct 77 ms 191060 KB ok
12 Correct 81 ms 191056 KB ok
13 Correct 77 ms 190948 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 191060 KB ok
2 Correct 80 ms 191120 KB ok
3 Correct 79 ms 191076 KB ok
4 Correct 72 ms 191060 KB ok
5 Correct 78 ms 190964 KB ok
6 Correct 76 ms 191056 KB ok
7 Correct 81 ms 191056 KB ok
8 Correct 83 ms 191120 KB ok
9 Correct 98 ms 191056 KB ok
10 Correct 92 ms 191056 KB ok
11 Correct 78 ms 190988 KB ok
12 Correct 77 ms 191060 KB ok
13 Correct 81 ms 191056 KB ok
14 Correct 77 ms 190948 KB ok
15 Correct 86 ms 190964 KB ok
16 Correct 81 ms 191080 KB ok
17 Correct 75 ms 191056 KB ok
18 Correct 97 ms 191068 KB ok
19 Correct 82 ms 191140 KB ok
20 Correct 77 ms 191056 KB ok
21 Correct 84 ms 191060 KB ok
22 Correct 77 ms 191056 KB ok
23 Correct 75 ms 191060 KB ok
24 Correct 71 ms 191060 KB ok
25 Correct 91 ms 191056 KB ok
26 Correct 73 ms 191056 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 191060 KB ok
2 Correct 80 ms 191120 KB ok
3 Correct 79 ms 191076 KB ok
4 Correct 79 ms 191056 KB ok
5 Correct 84 ms 191348 KB ok
6 Correct 72 ms 191060 KB ok
7 Correct 78 ms 190964 KB ok
8 Correct 76 ms 191056 KB ok
9 Correct 81 ms 191056 KB ok
10 Correct 83 ms 191120 KB ok
11 Correct 98 ms 191056 KB ok
12 Correct 92 ms 191056 KB ok
13 Correct 78 ms 190988 KB ok
14 Correct 77 ms 191060 KB ok
15 Correct 81 ms 191056 KB ok
16 Correct 77 ms 190948 KB ok
17 Correct 86 ms 190964 KB ok
18 Correct 81 ms 191080 KB ok
19 Correct 75 ms 191056 KB ok
20 Correct 97 ms 191068 KB ok
21 Correct 82 ms 191140 KB ok
22 Correct 77 ms 191056 KB ok
23 Correct 84 ms 191060 KB ok
24 Correct 77 ms 191056 KB ok
25 Correct 75 ms 191060 KB ok
26 Correct 71 ms 191060 KB ok
27 Correct 91 ms 191056 KB ok
28 Correct 73 ms 191056 KB ok
29 Correct 90 ms 191144 KB ok
30 Correct 75 ms 191124 KB ok
31 Correct 82 ms 191128 KB ok
32 Correct 75 ms 191056 KB ok
33 Correct 73 ms 191056 KB ok
34 Correct 86 ms 191060 KB ok
35 Correct 72 ms 190952 KB ok
36 Correct 74 ms 191056 KB ok
37 Correct 92 ms 190924 KB ok
38 Correct 73 ms 189648 KB ok
39 Correct 73 ms 189776 KB ok
40 Correct 71 ms 189780 KB ok
41 Correct 73 ms 189776 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 191060 KB ok
2 Correct 80 ms 191120 KB ok
3 Correct 79 ms 191076 KB ok
4 Correct 79 ms 191056 KB ok
5 Correct 84 ms 191348 KB ok
6 Correct 72 ms 191060 KB ok
7 Correct 78 ms 190964 KB ok
8 Correct 76 ms 191056 KB ok
9 Correct 81 ms 191056 KB ok
10 Correct 83 ms 191120 KB ok
11 Correct 98 ms 191056 KB ok
12 Correct 92 ms 191056 KB ok
13 Correct 78 ms 190988 KB ok
14 Correct 77 ms 191060 KB ok
15 Correct 81 ms 191056 KB ok
16 Correct 77 ms 190948 KB ok
17 Correct 86 ms 190964 KB ok
18 Correct 81 ms 191080 KB ok
19 Correct 75 ms 191056 KB ok
20 Correct 97 ms 191068 KB ok
21 Correct 82 ms 191140 KB ok
22 Correct 77 ms 191056 KB ok
23 Correct 84 ms 191060 KB ok
24 Correct 77 ms 191056 KB ok
25 Correct 75 ms 191060 KB ok
26 Correct 71 ms 191060 KB ok
27 Correct 91 ms 191056 KB ok
28 Correct 73 ms 191056 KB ok
29 Correct 90 ms 191144 KB ok
30 Correct 75 ms 191124 KB ok
31 Correct 82 ms 191128 KB ok
32 Correct 75 ms 191056 KB ok
33 Correct 73 ms 191056 KB ok
34 Correct 86 ms 191060 KB ok
35 Correct 72 ms 190952 KB ok
36 Correct 74 ms 191056 KB ok
37 Correct 92 ms 190924 KB ok
38 Correct 73 ms 189648 KB ok
39 Correct 73 ms 189776 KB ok
40 Correct 71 ms 189780 KB ok
41 Correct 73 ms 189776 KB ok
42 Correct 251 ms 226092 KB ok
43 Correct 205 ms 221120 KB ok
44 Correct 326 ms 234708 KB ok
45 Correct 258 ms 234444 KB ok
46 Correct 259 ms 229888 KB ok
47 Correct 199 ms 235340 KB ok
48 Correct 179 ms 213440 KB ok
49 Correct 183 ms 216484 KB ok
50 Correct 154 ms 215372 KB ok
51 Correct 199 ms 231616 KB ok
52 Correct 109 ms 199472 KB ok
53 Correct 94 ms 195940 KB ok
54 Correct 100 ms 199116 KB ok
55 Correct 117 ms 202696 KB ok
56 Correct 139 ms 211188 KB ok
57 Correct 209 ms 238452 KB ok
58 Correct 198 ms 237932 KB ok
59 Correct 213 ms 236216 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 191060 KB ok
2 Correct 80 ms 191120 KB ok
3 Correct 79 ms 191076 KB ok
4 Correct 79 ms 191056 KB ok
5 Correct 84 ms 191348 KB ok
6 Correct 82 ms 191032 KB ok
7 Correct 73 ms 191060 KB ok
8 Correct 100 ms 192812 KB ok
9 Correct 193 ms 236448 KB ok
10 Correct 1824 ms 923748 KB ok
11 Correct 72 ms 191060 KB ok
12 Correct 78 ms 190964 KB ok
13 Correct 76 ms 191056 KB ok
14 Correct 81 ms 191056 KB ok
15 Correct 83 ms 191120 KB ok
16 Correct 98 ms 191056 KB ok
17 Correct 92 ms 191056 KB ok
18 Correct 78 ms 190988 KB ok
19 Correct 77 ms 191060 KB ok
20 Correct 81 ms 191056 KB ok
21 Correct 77 ms 190948 KB ok
22 Correct 86 ms 190964 KB ok
23 Correct 81 ms 191080 KB ok
24 Correct 75 ms 191056 KB ok
25 Correct 97 ms 191068 KB ok
26 Correct 82 ms 191140 KB ok
27 Correct 77 ms 191056 KB ok
28 Correct 84 ms 191060 KB ok
29 Correct 77 ms 191056 KB ok
30 Correct 75 ms 191060 KB ok
31 Correct 71 ms 191060 KB ok
32 Correct 91 ms 191056 KB ok
33 Correct 73 ms 191056 KB ok
34 Correct 90 ms 191144 KB ok
35 Correct 75 ms 191124 KB ok
36 Correct 82 ms 191128 KB ok
37 Correct 75 ms 191056 KB ok
38 Correct 73 ms 191056 KB ok
39 Correct 86 ms 191060 KB ok
40 Correct 72 ms 190952 KB ok
41 Correct 74 ms 191056 KB ok
42 Correct 92 ms 190924 KB ok
43 Correct 73 ms 189648 KB ok
44 Correct 73 ms 189776 KB ok
45 Correct 71 ms 189780 KB ok
46 Correct 73 ms 189776 KB ok
47 Correct 251 ms 226092 KB ok
48 Correct 205 ms 221120 KB ok
49 Correct 326 ms 234708 KB ok
50 Correct 258 ms 234444 KB ok
51 Correct 259 ms 229888 KB ok
52 Correct 199 ms 235340 KB ok
53 Correct 179 ms 213440 KB ok
54 Correct 183 ms 216484 KB ok
55 Correct 154 ms 215372 KB ok
56 Correct 199 ms 231616 KB ok
57 Correct 109 ms 199472 KB ok
58 Correct 94 ms 195940 KB ok
59 Correct 100 ms 199116 KB ok
60 Correct 117 ms 202696 KB ok
61 Correct 139 ms 211188 KB ok
62 Correct 209 ms 238452 KB ok
63 Correct 198 ms 237932 KB ok
64 Correct 213 ms 236216 KB ok
65 Correct 3150 ms 783332 KB ok
66 Correct 754 ms 337328 KB ok
67 Correct 434 ms 255816 KB ok
68 Execution timed out 4567 ms 911380 KB Time limit exceeded
69 Halted 0 ms 0 KB -