oj.uz

Submission #1068125

# Submission time Handle Problem Language Result Execution time Memory
1068125 2024-08-21T07:52:29 Z AdamGS Soccer Stadium (IOI23_soccer) C++17
8 / 100
 4500 ms 1090096 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)});
			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 75 ms 189520 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 189524 KB ok
2 Correct 73 ms 189464 KB ok
3 Correct 76 ms 189524 KB ok
4 Correct 76 ms 189520 KB ok
5 Correct 74 ms 189524 KB ok
6 Correct 80 ms 189520 KB ok
7 Correct 90 ms 191824 KB ok
8 Correct 339 ms 245724 KB ok
9 Execution timed out 4616 ms 1090096 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 189524 KB ok
2 Correct 73 ms 189464 KB ok
3 Correct 79 ms 189520 KB ok
4 Correct 76 ms 189516 KB ok
5 Correct 81 ms 189524 KB ok
6 Correct 73 ms 189524 KB ok
7 Correct 87 ms 189476 KB ok
8 Correct 87 ms 189520 KB ok
9 Correct 84 ms 189640 KB ok
10 Correct 81 ms 189520 KB ok
11 Correct 82 ms 189524 KB ok
12 Correct 109 ms 189524 KB ok
13 Correct 88 ms 189560 KB ok

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 189520 KB ok
2 Correct 75 ms 189524 KB ok
3 Correct 73 ms 189464 KB ok
4 Correct 79 ms 189520 KB ok
5 Correct 76 ms 189516 KB ok
6 Correct 81 ms 189524 KB ok
7 Correct 73 ms 189524 KB ok
8 Correct 87 ms 189476 KB ok
9 Correct 87 ms 189520 KB ok
10 Correct 84 ms 189640 KB ok
11 Correct 81 ms 189520 KB ok
12 Correct 82 ms 189524 KB ok
13 Correct 109 ms 189524 KB ok
14 Correct 88 ms 189560 KB ok
15 Correct 75 ms 189612 KB ok
16 Correct 87 ms 189524 KB ok
17 Partially correct 99 ms 189520 KB partial
18 Correct 75 ms 189520 KB ok
19 Correct 75 ms 189520 KB ok
20 Incorrect 80 ms 189608 KB wrong
21 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 189520 KB ok
2 Correct 75 ms 189524 KB ok
3 Correct 73 ms 189464 KB ok
4 Correct 76 ms 189524 KB ok
5 Correct 76 ms 189520 KB ok
6 Correct 79 ms 189520 KB ok
7 Correct 76 ms 189516 KB ok
8 Correct 81 ms 189524 KB ok
9 Correct 73 ms 189524 KB ok
10 Correct 87 ms 189476 KB ok
11 Correct 87 ms 189520 KB ok
12 Correct 84 ms 189640 KB ok
13 Correct 81 ms 189520 KB ok
14 Correct 82 ms 189524 KB ok
15 Correct 109 ms 189524 KB ok
16 Correct 88 ms 189560 KB ok
17 Correct 75 ms 189612 KB ok
18 Correct 87 ms 189524 KB ok
19 Partially correct 99 ms 189520 KB partial
20 Correct 75 ms 189520 KB ok
21 Correct 75 ms 189520 KB ok
22 Incorrect 80 ms 189608 KB wrong
23 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 189520 KB ok
2 Correct 75 ms 189524 KB ok
3 Correct 73 ms 189464 KB ok
4 Correct 76 ms 189524 KB ok
5 Correct 76 ms 189520 KB ok
6 Correct 79 ms 189520 KB ok
7 Correct 76 ms 189516 KB ok
8 Correct 81 ms 189524 KB ok
9 Correct 73 ms 189524 KB ok
10 Correct 87 ms 189476 KB ok
11 Correct 87 ms 189520 KB ok
12 Correct 84 ms 189640 KB ok
13 Correct 81 ms 189520 KB ok
14 Correct 82 ms 189524 KB ok
15 Correct 109 ms 189524 KB ok
16 Correct 88 ms 189560 KB ok
17 Correct 75 ms 189612 KB ok
18 Correct 87 ms 189524 KB ok
19 Partially correct 99 ms 189520 KB partial
20 Correct 75 ms 189520 KB ok
21 Correct 75 ms 189520 KB ok
22 Incorrect 80 ms 189608 KB wrong
23 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 189520 KB ok
2 Correct 75 ms 189524 KB ok
3 Correct 73 ms 189464 KB ok
4 Correct 76 ms 189524 KB ok
5 Correct 76 ms 189520 KB ok
6 Correct 74 ms 189524 KB ok
7 Correct 80 ms 189520 KB ok
8 Correct 90 ms 191824 KB ok
9 Correct 339 ms 245724 KB ok
10 Execution timed out 4616 ms 1090096 KB Time limit exceeded
11 Halted 0 ms 0 KB -