oj.uz

Submission #1068152

# Submission time Handle Problem Language Result Execution time Memory
1068152 2024-08-21T08:04:17 Z AdamGS Soccer Stadium (IOI23_soccer) C++17
64 / 100
 4500 ms 991720 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()
const int LIM=2e3+7;
map<pair<pair<int,int>,pair<int,int>>,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}};
			if(!mp[x]) {
				mp[x]=++akt;
				pole.pb((x.st.nd-x.st.st+1)*(x.nd.st-x.nd.nd+1));
			}
			int k=mp[x];
			for(auto c : A) V[k].pb({mp[c], (c.st.nd-c.st.st+1)*(x.nd.nd-c.nd.nd)});	
			if(j>1) V[mp[{{a, b}, {i-1, i-j+1}}]].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}};
			if(!mp[x]) {
				mp[x]=++akt;
				pole.pb((x.st.nd-x.st.st+1)*(x.nd.st-x.nd.nd+1));
			}
			int k=mp[x];
			for(auto c : A) {
				V[k].pb({mp[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 73 ms 189524 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 189520 KB ok
2 Correct 81 ms 189604 KB ok
3 Correct 78 ms 189524 KB ok
4 Correct 74 ms 189524 KB ok
5 Correct 83 ms 189560 KB ok
6 Correct 75 ms 189468 KB ok
7 Correct 82 ms 191820 KB ok
8 Correct 358 ms 245440 KB ok
9 Execution timed out 4562 ms 991720 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 189520 KB ok
2 Correct 81 ms 189604 KB ok
3 Correct 75 ms 189556 KB ok
4 Correct 79 ms 189524 KB ok
5 Correct 85 ms 189520 KB ok
6 Correct 73 ms 189524 KB ok
7 Correct 70 ms 189520 KB ok
8 Correct 69 ms 189520 KB ok
9 Correct 99 ms 189528 KB ok
10 Correct 96 ms 189528 KB ok
11 Correct 93 ms 189520 KB ok
12 Correct 68 ms 189520 KB ok
13 Correct 96 ms 189528 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 189524 KB ok
2 Correct 80 ms 189520 KB ok
3 Correct 81 ms 189604 KB ok
4 Correct 75 ms 189556 KB ok
5 Correct 79 ms 189524 KB ok
6 Correct 85 ms 189520 KB ok
7 Correct 73 ms 189524 KB ok
8 Correct 70 ms 189520 KB ok
9 Correct 69 ms 189520 KB ok
10 Correct 99 ms 189528 KB ok
11 Correct 96 ms 189528 KB ok
12 Correct 93 ms 189520 KB ok
13 Correct 68 ms 189520 KB ok
14 Correct 96 ms 189528 KB ok
15 Correct 101 ms 189524 KB ok
16 Correct 88 ms 189548 KB ok
17 Correct 75 ms 189572 KB ok
18 Correct 83 ms 189484 KB ok
19 Correct 77 ms 189572 KB ok
20 Correct 73 ms 189660 KB ok
21 Correct 75 ms 189468 KB ok
22 Correct 78 ms 189520 KB ok
23 Correct 88 ms 189520 KB ok
24 Correct 75 ms 189532 KB ok
25 Correct 77 ms 189580 KB ok
26 Correct 78 ms 189596 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 189524 KB ok
2 Correct 80 ms 189520 KB ok
3 Correct 81 ms 189604 KB ok
4 Correct 78 ms 189524 KB ok
5 Correct 74 ms 189524 KB ok
6 Correct 75 ms 189556 KB ok
7 Correct 79 ms 189524 KB ok
8 Correct 85 ms 189520 KB ok
9 Correct 73 ms 189524 KB ok
10 Correct 70 ms 189520 KB ok
11 Correct 69 ms 189520 KB ok
12 Correct 99 ms 189528 KB ok
13 Correct 96 ms 189528 KB ok
14 Correct 93 ms 189520 KB ok
15 Correct 68 ms 189520 KB ok
16 Correct 96 ms 189528 KB ok
17 Correct 101 ms 189524 KB ok
18 Correct 88 ms 189548 KB ok
19 Correct 75 ms 189572 KB ok
20 Correct 83 ms 189484 KB ok
21 Correct 77 ms 189572 KB ok
22 Correct 73 ms 189660 KB ok
23 Correct 75 ms 189468 KB ok
24 Correct 78 ms 189520 KB ok
25 Correct 88 ms 189520 KB ok
26 Correct 75 ms 189532 KB ok
27 Correct 77 ms 189580 KB ok
28 Correct 78 ms 189596 KB ok
29 Correct 103 ms 189524 KB ok
30 Correct 71 ms 189668 KB ok
31 Correct 97 ms 189644 KB ok
32 Correct 81 ms 189744 KB ok
33 Correct 75 ms 189520 KB ok
34 Correct 75 ms 189524 KB ok
35 Correct 74 ms 189620 KB ok
36 Correct 84 ms 189628 KB ok
37 Correct 80 ms 189536 KB ok
38 Correct 78 ms 189524 KB ok
39 Correct 76 ms 189496 KB ok
40 Correct 99 ms 189580 KB ok
41 Correct 79 ms 189632 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 189524 KB ok
2 Correct 80 ms 189520 KB ok
3 Correct 81 ms 189604 KB ok
4 Correct 78 ms 189524 KB ok
5 Correct 74 ms 189524 KB ok
6 Correct 75 ms 189556 KB ok
7 Correct 79 ms 189524 KB ok
8 Correct 85 ms 189520 KB ok
9 Correct 73 ms 189524 KB ok
10 Correct 70 ms 189520 KB ok
11 Correct 69 ms 189520 KB ok
12 Correct 99 ms 189528 KB ok
13 Correct 96 ms 189528 KB ok
14 Correct 93 ms 189520 KB ok
15 Correct 68 ms 189520 KB ok
16 Correct 96 ms 189528 KB ok
17 Correct 101 ms 189524 KB ok
18 Correct 88 ms 189548 KB ok
19 Correct 75 ms 189572 KB ok
20 Correct 83 ms 189484 KB ok
21 Correct 77 ms 189572 KB ok
22 Correct 73 ms 189660 KB ok
23 Correct 75 ms 189468 KB ok
24 Correct 78 ms 189520 KB ok
25 Correct 88 ms 189520 KB ok
26 Correct 75 ms 189532 KB ok
27 Correct 77 ms 189580 KB ok
28 Correct 78 ms 189596 KB ok
29 Correct 103 ms 189524 KB ok
30 Correct 71 ms 189668 KB ok
31 Correct 97 ms 189644 KB ok
32 Correct 81 ms 189744 KB ok
33 Correct 75 ms 189520 KB ok
34 Correct 75 ms 189524 KB ok
35 Correct 74 ms 189620 KB ok
36 Correct 84 ms 189628 KB ok
37 Correct 80 ms 189536 KB ok
38 Correct 78 ms 189524 KB ok
39 Correct 76 ms 189496 KB ok
40 Correct 99 ms 189580 KB ok
41 Correct 79 ms 189632 KB ok
42 Correct 631 ms 235044 KB ok
43 Correct 566 ms 227672 KB ok
44 Correct 767 ms 242432 KB ok
45 Correct 712 ms 243216 KB ok
46 Correct 767 ms 239292 KB ok
47 Correct 379 ms 245440 KB ok
48 Correct 291 ms 218052 KB ok
49 Correct 295 ms 220104 KB ok
50 Correct 268 ms 223684 KB ok
51 Correct 446 ms 239296 KB ok
52 Correct 142 ms 198816 KB ok
53 Correct 109 ms 194504 KB ok
54 Correct 138 ms 198352 KB ok
55 Correct 165 ms 202808 KB ok
56 Correct 209 ms 213544 KB ok
57 Correct 443 ms 247088 KB ok
58 Correct 453 ms 246572 KB ok
59 Correct 431 ms 246316 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 189524 KB ok
2 Correct 80 ms 189520 KB ok
3 Correct 81 ms 189604 KB ok
4 Correct 78 ms 189524 KB ok
5 Correct 74 ms 189524 KB ok
6 Correct 83 ms 189560 KB ok
7 Correct 75 ms 189468 KB ok
8 Correct 82 ms 191820 KB ok
9 Correct 358 ms 245440 KB ok
10 Execution timed out 4562 ms 991720 KB Time limit exceeded
11 Halted 0 ms 0 KB -