Submission #839947

#	Time	Username	Problem	Language	Result	Execution time	Memory
839947		zscoder	Soccer Stadium (IOI23_soccer)	C++17	64 / 100	800 ms	767780 KiB

soccer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef bitset<500> b100;

int a[2011][2011];
int dp[511][511][511];
ii iv[2011][2011];
int L[511][511][511];
int R[511][511][511];

int intersect(ii a, ii b)
{
	int l=max(a.fi,b.fi); int r=min(a.se,b.se);
	return max(0,r-l+1);
}

int biggest_stadium(int n, vector<vector<int> > F)
{
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			a[i][j]=F[i][j]; a[i][j]=1-a[i][j];
		}
	}
	for(int i=0;i<n;i++)
	{
		vector<ii> intervals;
		int st=-1;
		for(int j=0;j<n+1;j++)
		{
			if(a[i][j])
			{
				if(st==-1)
				{
					st=j;
				}
				//else st continues;
			}
			else
			{
				iv[i][j]={-1,-1};
				if(st!=-1)
				{
					intervals.pb({st,j-1});
					for(int k=st;k<j;k++)
					{
						iv[i][k]={st,j-1};
					}
					st=-1;
				}
			}
		}
	}
	int ans=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			L[i][i][j]=(iv[i][j].fi==-1?int(1e9):iv[i][j].fi);
			R[i][i][j]=iv[i][j].se;
			dp[i][i][j]=max(R[i][i][j]-L[i][i][j]+1,0);
			ans=max(ans,dp[i][i][j]);
			//cerr<<i<<' '<<j<<' '<<L[i][i][j]<<' '<<R[i][i][j]<<' '<<dp[i][i][j]<<'\n';
		}
	}
	
	for(int len=2;len<=n;len++)
	{
		for(int l=0;l+len-1<n;l++)
		{
			int r=l+len-1;
			for(int j=0;j<n;j++)
			{
				int l1 = max(L[l+1][r][j],iv[l][j].fi);
				int l2 = max(L[l][r-1][j],iv[r][j].fi);
				L[l][r][j]=min(l1,l2);
				int r1 = min(R[l+1][r][j],iv[l][j].se);
				int r2 = min(R[l][r-1][j],iv[r][j].se);
				R[l][r][j]=max(r1,r2);
				dp[l][r][j]=max(dp[l+1][r][j]+intersect({L[l+1][r][j],R[l+1][r][j]},{L[l][l][j],R[l][l][j]}),
								dp[l][r-1][j]+intersect({L[l][r-1][j],R[l][r-1][j]},{L[r][r][j],R[r][r][j]}));
				ans=max(ans,dp[l][r][j]);
			}
			//L[l][r][
		}
	}
	return ans;
}
/*
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	
}
*/

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 8 / 8
• Subtask 3: 22 / 22
• Subtask 4: 18 / 18
• Subtask 5: 16 / 16
• Subtask 6: 0 / 30