oj.uz

Submission #1068175

# Submission time Handle Problem Language Result Execution time Memory
1068175 2024-08-21T08:16:26 Z AdamGS Soccer Stadium (IOI23_soccer) C++17
70 / 100
 4500 ms 934120 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)*LIM)+x.nd.nd)
const ll LIM=2e3+7;
unordered_map<ll,int>mp;
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[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[koduj(c)], (c.st.nd-c.st.st+1)*(x.nd.nd-c.nd.nd)});	
			if(j>1) {
				--x.nd.st;
				V[mp[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[koduj(x)];
			if(!k) {
				mp[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[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 76 ms 189608 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 189536 KB ok
2 Correct 82 ms 189524 KB ok
3 Correct 83 ms 189664 KB ok
4 Correct 84 ms 189524 KB ok
5 Correct 76 ms 189524 KB ok
6 Correct 81 ms 189524 KB ok
7 Correct 87 ms 191312 KB ok
8 Correct 181 ms 235956 KB ok
9 Correct 2539 ms 934120 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 189536 KB ok
2 Correct 82 ms 189524 KB ok
3 Correct 83 ms 189576 KB ok
4 Correct 75 ms 189556 KB ok
5 Correct 81 ms 189524 KB ok
6 Correct 77 ms 189520 KB ok
7 Correct 76 ms 189524 KB ok
8 Correct 75 ms 189520 KB ok
9 Correct 75 ms 189652 KB ok
10 Correct 83 ms 189444 KB ok
11 Correct 86 ms 189524 KB ok
12 Correct 79 ms 189524 KB ok
13 Correct 74 ms 189524 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 189608 KB ok
2 Correct 77 ms 189536 KB ok
3 Correct 82 ms 189524 KB ok
4 Correct 83 ms 189576 KB ok
5 Correct 75 ms 189556 KB ok
6 Correct 81 ms 189524 KB ok
7 Correct 77 ms 189520 KB ok
8 Correct 76 ms 189524 KB ok
9 Correct 75 ms 189520 KB ok
10 Correct 75 ms 189652 KB ok
11 Correct 83 ms 189444 KB ok
12 Correct 86 ms 189524 KB ok
13 Correct 79 ms 189524 KB ok
14 Correct 74 ms 189524 KB ok
15 Correct 86 ms 189524 KB ok
16 Correct 86 ms 189524 KB ok
17 Correct 86 ms 189520 KB ok
18 Correct 82 ms 189628 KB ok
19 Correct 82 ms 189472 KB ok
20 Correct 83 ms 189776 KB ok
21 Correct 91 ms 189540 KB ok
22 Correct 76 ms 189520 KB ok
23 Correct 80 ms 189520 KB ok
24 Correct 79 ms 189528 KB ok
25 Correct 81 ms 189636 KB ok
26 Correct 76 ms 189508 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 189608 KB ok
2 Correct 77 ms 189536 KB ok
3 Correct 82 ms 189524 KB ok
4 Correct 83 ms 189664 KB ok
5 Correct 84 ms 189524 KB ok
6 Correct 83 ms 189576 KB ok
7 Correct 75 ms 189556 KB ok
8 Correct 81 ms 189524 KB ok
9 Correct 77 ms 189520 KB ok
10 Correct 76 ms 189524 KB ok
11 Correct 75 ms 189520 KB ok
12 Correct 75 ms 189652 KB ok
13 Correct 83 ms 189444 KB ok
14 Correct 86 ms 189524 KB ok
15 Correct 79 ms 189524 KB ok
16 Correct 74 ms 189524 KB ok
17 Correct 86 ms 189524 KB ok
18 Correct 86 ms 189524 KB ok
19 Correct 86 ms 189520 KB ok
20 Correct 82 ms 189628 KB ok
21 Correct 82 ms 189472 KB ok
22 Correct 83 ms 189776 KB ok
23 Correct 91 ms 189540 KB ok
24 Correct 76 ms 189520 KB ok
25 Correct 80 ms 189520 KB ok
26 Correct 79 ms 189528 KB ok
27 Correct 81 ms 189636 KB ok
28 Correct 76 ms 189508 KB ok
29 Correct 83 ms 189644 KB ok
30 Correct 82 ms 189776 KB ok
31 Correct 83 ms 189772 KB ok
32 Correct 80 ms 189568 KB ok
33 Correct 79 ms 189516 KB ok
34 Correct 81 ms 189632 KB ok
35 Correct 86 ms 189528 KB ok
36 Correct 90 ms 189696 KB ok
37 Correct 87 ms 189520 KB ok
38 Correct 87 ms 189516 KB ok
39 Correct 84 ms 189524 KB ok
40 Correct 89 ms 189776 KB ok
41 Correct 98 ms 189780 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 189608 KB ok
2 Correct 77 ms 189536 KB ok
3 Correct 82 ms 189524 KB ok
4 Correct 83 ms 189664 KB ok
5 Correct 84 ms 189524 KB ok
6 Correct 83 ms 189576 KB ok
7 Correct 75 ms 189556 KB ok
8 Correct 81 ms 189524 KB ok
9 Correct 77 ms 189520 KB ok
10 Correct 76 ms 189524 KB ok
11 Correct 75 ms 189520 KB ok
12 Correct 75 ms 189652 KB ok
13 Correct 83 ms 189444 KB ok
14 Correct 86 ms 189524 KB ok
15 Correct 79 ms 189524 KB ok
16 Correct 74 ms 189524 KB ok
17 Correct 86 ms 189524 KB ok
18 Correct 86 ms 189524 KB ok
19 Correct 86 ms 189520 KB ok
20 Correct 82 ms 189628 KB ok
21 Correct 82 ms 189472 KB ok
22 Correct 83 ms 189776 KB ok
23 Correct 91 ms 189540 KB ok
24 Correct 76 ms 189520 KB ok
25 Correct 80 ms 189520 KB ok
26 Correct 79 ms 189528 KB ok
27 Correct 81 ms 189636 KB ok
28 Correct 76 ms 189508 KB ok
29 Correct 83 ms 189644 KB ok
30 Correct 82 ms 189776 KB ok
31 Correct 83 ms 189772 KB ok
32 Correct 80 ms 189568 KB ok
33 Correct 79 ms 189516 KB ok
34 Correct 81 ms 189632 KB ok
35 Correct 86 ms 189528 KB ok
36 Correct 90 ms 189696 KB ok
37 Correct 87 ms 189520 KB ok
38 Correct 87 ms 189516 KB ok
39 Correct 84 ms 189524 KB ok
40 Correct 89 ms 189776 KB ok
41 Correct 98 ms 189780 KB ok
42 Correct 271 ms 227484 KB ok
43 Correct 232 ms 221992 KB ok
44 Correct 288 ms 232992 KB ok
45 Correct 331 ms 233756 KB ok
46 Correct 304 ms 230436 KB ok
47 Correct 212 ms 235688 KB ok
48 Correct 163 ms 213456 KB ok
49 Correct 223 ms 214764 KB ok
50 Correct 252 ms 215280 KB ok
51 Correct 247 ms 230368 KB ok
52 Correct 123 ms 197808 KB ok
53 Correct 107 ms 194476 KB ok
54 Correct 116 ms 197596 KB ok
55 Correct 126 ms 201276 KB ok
56 Correct 147 ms 210416 KB ok
57 Correct 255 ms 235452 KB ok
58 Correct 255 ms 235088 KB ok
59 Correct 264 ms 234904 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 189608 KB ok
2 Correct 77 ms 189536 KB ok
3 Correct 82 ms 189524 KB ok
4 Correct 83 ms 189664 KB ok
5 Correct 84 ms 189524 KB ok
6 Correct 76 ms 189524 KB ok
7 Correct 81 ms 189524 KB ok
8 Correct 87 ms 191312 KB ok
9 Correct 181 ms 235956 KB ok
10 Correct 2539 ms 934120 KB ok
11 Correct 83 ms 189576 KB ok
12 Correct 75 ms 189556 KB ok
13 Correct 81 ms 189524 KB ok
14 Correct 77 ms 189520 KB ok
15 Correct 76 ms 189524 KB ok
16 Correct 75 ms 189520 KB ok
17 Correct 75 ms 189652 KB ok
18 Correct 83 ms 189444 KB ok
19 Correct 86 ms 189524 KB ok
20 Correct 79 ms 189524 KB ok
21 Correct 74 ms 189524 KB ok
22 Correct 86 ms 189524 KB ok
23 Correct 86 ms 189524 KB ok
24 Correct 86 ms 189520 KB ok
25 Correct 82 ms 189628 KB ok
26 Correct 82 ms 189472 KB ok
27 Correct 83 ms 189776 KB ok
28 Correct 91 ms 189540 KB ok
29 Correct 76 ms 189520 KB ok
30 Correct 80 ms 189520 KB ok
31 Correct 79 ms 189528 KB ok
32 Correct 81 ms 189636 KB ok
33 Correct 76 ms 189508 KB ok
34 Correct 83 ms 189644 KB ok
35 Correct 82 ms 189776 KB ok
36 Correct 83 ms 189772 KB ok
37 Correct 80 ms 189568 KB ok
38 Correct 79 ms 189516 KB ok
39 Correct 81 ms 189632 KB ok
40 Correct 86 ms 189528 KB ok
41 Correct 90 ms 189696 KB ok
42 Correct 87 ms 189520 KB ok
43 Correct 87 ms 189516 KB ok
44 Correct 84 ms 189524 KB ok
45 Correct 89 ms 189776 KB ok
46 Correct 98 ms 189780 KB ok
47 Correct 271 ms 227484 KB ok
48 Correct 232 ms 221992 KB ok
49 Correct 288 ms 232992 KB ok
50 Correct 331 ms 233756 KB ok
51 Correct 304 ms 230436 KB ok
52 Correct 212 ms 235688 KB ok
53 Correct 163 ms 213456 KB ok
54 Correct 223 ms 214764 KB ok
55 Correct 252 ms 215280 KB ok
56 Correct 247 ms 230368 KB ok
57 Correct 123 ms 197808 KB ok
58 Correct 107 ms 194476 KB ok
59 Correct 116 ms 197596 KB ok
60 Correct 126 ms 201276 KB ok
61 Correct 147 ms 210416 KB ok
62 Correct 255 ms 235452 KB ok
63 Correct 255 ms 235088 KB ok
64 Correct 264 ms 234904 KB ok
65 Execution timed out 4613 ms 729860 KB Time limit exceeded
66 Halted 0 ms 0 KB -