oj.uz

Submission #1068172

# Submission time Handle Problem Language Result Execution time Memory
1068172 2024-08-21T08:14:00 Z AdamGS Soccer Stadium (IOI23_soccer) C++17
70 / 100
 4500 ms 934616 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=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)*(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 97 ms 189536 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 189460 KB ok
2 Correct 78 ms 189520 KB ok
3 Correct 109 ms 189692 KB ok
4 Correct 77 ms 189528 KB ok
5 Correct 80 ms 189524 KB ok
6 Correct 78 ms 189532 KB ok
7 Correct 87 ms 191436 KB ok
8 Correct 188 ms 235816 KB ok
9 Correct 2497 ms 934616 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 189460 KB ok
2 Correct 78 ms 189520 KB ok
3 Correct 76 ms 189524 KB ok
4 Correct 80 ms 189520 KB ok
5 Correct 79 ms 189448 KB ok
6 Correct 103 ms 189452 KB ok
7 Correct 75 ms 189524 KB ok
8 Correct 96 ms 189444 KB ok
9 Correct 101 ms 189636 KB ok
10 Correct 76 ms 189520 KB ok
11 Correct 85 ms 189524 KB ok
12 Correct 73 ms 189488 KB ok
13 Correct 76 ms 189552 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 189536 KB ok
2 Correct 79 ms 189460 KB ok
3 Correct 78 ms 189520 KB ok
4 Correct 76 ms 189524 KB ok
5 Correct 80 ms 189520 KB ok
6 Correct 79 ms 189448 KB ok
7 Correct 103 ms 189452 KB ok
8 Correct 75 ms 189524 KB ok
9 Correct 96 ms 189444 KB ok
10 Correct 101 ms 189636 KB ok
11 Correct 76 ms 189520 KB ok
12 Correct 85 ms 189524 KB ok
13 Correct 73 ms 189488 KB ok
14 Correct 76 ms 189552 KB ok
15 Correct 84 ms 189520 KB ok
16 Correct 75 ms 189520 KB ok
17 Correct 87 ms 189520 KB ok
18 Correct 97 ms 189524 KB ok
19 Correct 92 ms 189520 KB ok
20 Correct 92 ms 189524 KB ok
21 Correct 100 ms 189608 KB ok
22 Correct 89 ms 189600 KB ok
23 Correct 96 ms 189520 KB ok
24 Correct 106 ms 189496 KB ok
25 Correct 107 ms 189524 KB ok
26 Correct 95 ms 189524 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 189536 KB ok
2 Correct 79 ms 189460 KB ok
3 Correct 78 ms 189520 KB ok
4 Correct 109 ms 189692 KB ok
5 Correct 77 ms 189528 KB ok
6 Correct 76 ms 189524 KB ok
7 Correct 80 ms 189520 KB ok
8 Correct 79 ms 189448 KB ok
9 Correct 103 ms 189452 KB ok
10 Correct 75 ms 189524 KB ok
11 Correct 96 ms 189444 KB ok
12 Correct 101 ms 189636 KB ok
13 Correct 76 ms 189520 KB ok
14 Correct 85 ms 189524 KB ok
15 Correct 73 ms 189488 KB ok
16 Correct 76 ms 189552 KB ok
17 Correct 84 ms 189520 KB ok
18 Correct 75 ms 189520 KB ok
19 Correct 87 ms 189520 KB ok
20 Correct 97 ms 189524 KB ok
21 Correct 92 ms 189520 KB ok
22 Correct 92 ms 189524 KB ok
23 Correct 100 ms 189608 KB ok
24 Correct 89 ms 189600 KB ok
25 Correct 96 ms 189520 KB ok
26 Correct 106 ms 189496 KB ok
27 Correct 107 ms 189524 KB ok
28 Correct 95 ms 189524 KB ok
29 Correct 104 ms 189516 KB ok
30 Correct 87 ms 189776 KB ok
31 Correct 90 ms 189648 KB ok
32 Correct 68 ms 189520 KB ok
33 Correct 69 ms 189520 KB ok
34 Correct 102 ms 189664 KB ok
35 Correct 66 ms 189520 KB ok
36 Correct 76 ms 189632 KB ok
37 Correct 103 ms 189520 KB ok
38 Correct 92 ms 189712 KB ok
39 Correct 76 ms 189520 KB ok
40 Correct 100 ms 189780 KB ok
41 Correct 97 ms 189624 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 189536 KB ok
2 Correct 79 ms 189460 KB ok
3 Correct 78 ms 189520 KB ok
4 Correct 109 ms 189692 KB ok
5 Correct 77 ms 189528 KB ok
6 Correct 76 ms 189524 KB ok
7 Correct 80 ms 189520 KB ok
8 Correct 79 ms 189448 KB ok
9 Correct 103 ms 189452 KB ok
10 Correct 75 ms 189524 KB ok
11 Correct 96 ms 189444 KB ok
12 Correct 101 ms 189636 KB ok
13 Correct 76 ms 189520 KB ok
14 Correct 85 ms 189524 KB ok
15 Correct 73 ms 189488 KB ok
16 Correct 76 ms 189552 KB ok
17 Correct 84 ms 189520 KB ok
18 Correct 75 ms 189520 KB ok
19 Correct 87 ms 189520 KB ok
20 Correct 97 ms 189524 KB ok
21 Correct 92 ms 189520 KB ok
22 Correct 92 ms 189524 KB ok
23 Correct 100 ms 189608 KB ok
24 Correct 89 ms 189600 KB ok
25 Correct 96 ms 189520 KB ok
26 Correct 106 ms 189496 KB ok
27 Correct 107 ms 189524 KB ok
28 Correct 95 ms 189524 KB ok
29 Correct 104 ms 189516 KB ok
30 Correct 87 ms 189776 KB ok
31 Correct 90 ms 189648 KB ok
32 Correct 68 ms 189520 KB ok
33 Correct 69 ms 189520 KB ok
34 Correct 102 ms 189664 KB ok
35 Correct 66 ms 189520 KB ok
36 Correct 76 ms 189632 KB ok
37 Correct 103 ms 189520 KB ok
38 Correct 92 ms 189712 KB ok
39 Correct 76 ms 189520 KB ok
40 Correct 100 ms 189780 KB ok
41 Correct 97 ms 189624 KB ok
42 Correct 407 ms 227116 KB ok
43 Correct 330 ms 222100 KB ok
44 Correct 384 ms 233092 KB ok
45 Correct 373 ms 233768 KB ok
46 Correct 354 ms 230320 KB ok
47 Correct 201 ms 235704 KB ok
48 Correct 215 ms 213236 KB ok
49 Correct 194 ms 214756 KB ok
50 Correct 223 ms 215268 KB ok
51 Correct 328 ms 230444 KB ok
52 Correct 107 ms 197852 KB ok
53 Correct 105 ms 194476 KB ok
54 Correct 116 ms 197556 KB ok
55 Correct 160 ms 201360 KB ok
56 Correct 149 ms 210420 KB ok
57 Correct 270 ms 235524 KB ok
58 Correct 264 ms 235200 KB ok
59 Correct 282 ms 234984 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 189536 KB ok
2 Correct 79 ms 189460 KB ok
3 Correct 78 ms 189520 KB ok
4 Correct 109 ms 189692 KB ok
5 Correct 77 ms 189528 KB ok
6 Correct 80 ms 189524 KB ok
7 Correct 78 ms 189532 KB ok
8 Correct 87 ms 191436 KB ok
9 Correct 188 ms 235816 KB ok
10 Correct 2497 ms 934616 KB ok
11 Correct 76 ms 189524 KB ok
12 Correct 80 ms 189520 KB ok
13 Correct 79 ms 189448 KB ok
14 Correct 103 ms 189452 KB ok
15 Correct 75 ms 189524 KB ok
16 Correct 96 ms 189444 KB ok
17 Correct 101 ms 189636 KB ok
18 Correct 76 ms 189520 KB ok
19 Correct 85 ms 189524 KB ok
20 Correct 73 ms 189488 KB ok
21 Correct 76 ms 189552 KB ok
22 Correct 84 ms 189520 KB ok
23 Correct 75 ms 189520 KB ok
24 Correct 87 ms 189520 KB ok
25 Correct 97 ms 189524 KB ok
26 Correct 92 ms 189520 KB ok
27 Correct 92 ms 189524 KB ok
28 Correct 100 ms 189608 KB ok
29 Correct 89 ms 189600 KB ok
30 Correct 96 ms 189520 KB ok
31 Correct 106 ms 189496 KB ok
32 Correct 107 ms 189524 KB ok
33 Correct 95 ms 189524 KB ok
34 Correct 104 ms 189516 KB ok
35 Correct 87 ms 189776 KB ok
36 Correct 90 ms 189648 KB ok
37 Correct 68 ms 189520 KB ok
38 Correct 69 ms 189520 KB ok
39 Correct 102 ms 189664 KB ok
40 Correct 66 ms 189520 KB ok
41 Correct 76 ms 189632 KB ok
42 Correct 103 ms 189520 KB ok
43 Correct 92 ms 189712 KB ok
44 Correct 76 ms 189520 KB ok
45 Correct 100 ms 189780 KB ok
46 Correct 97 ms 189624 KB ok
47 Correct 407 ms 227116 KB ok
48 Correct 330 ms 222100 KB ok
49 Correct 384 ms 233092 KB ok
50 Correct 373 ms 233768 KB ok
51 Correct 354 ms 230320 KB ok
52 Correct 201 ms 235704 KB ok
53 Correct 215 ms 213236 KB ok
54 Correct 194 ms 214756 KB ok
55 Correct 223 ms 215268 KB ok
56 Correct 328 ms 230444 KB ok
57 Correct 107 ms 197852 KB ok
58 Correct 105 ms 194476 KB ok
59 Correct 116 ms 197556 KB ok
60 Correct 160 ms 201360 KB ok
61 Correct 149 ms 210420 KB ok
62 Correct 270 ms 235524 KB ok
63 Correct 264 ms 235200 KB ok
64 Correct 282 ms 234984 KB ok
65 Execution timed out 4581 ms 733600 KB Time limit exceeded
66 Halted 0 ms 0 KB -