Submission #1068125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068125		AdamGS	Soccer Stadium (IOI23_soccer)	C++17	8 / 100	4616 ms	1090096 KiB

soccer

#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
• Subtask 1: 0 / 6
• Subtask 2: 8 / 8
• Subtask 3: 0 / 22
• Subtask 4: 0 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30