Submission #840869

#	Time	Username	Problem	Language	Result	Execution time	Memory
840869		Edu175	Soccer Stadium (IOI23_soccer)	C++17	64 / 100	4583 ms	896324 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ggdem=b;i<ggdem;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define imp(v) for(auto messi:v)cout<<messi<<" "; cout<<"\n"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll MAXN=2005;

ll n;
ll a[MAXN][MAXN],b[MAXN][MAXN];

ll oper(ll a, ll b){
	return max(a,b);
}
ll K=11;
struct ST{
	vector<vector<ll>>st; ll n;
	//ST(ll n):st(K,vector<ll>(1<<K)),n(n){}
	ST(){}
	void init(vector<ll>a){
		n=SZ(a);
		st.resize(K,vector<ll>(1<<K));
		fore(i,0,n)st[0][i]=a[i];
		fore(k,1,K)fore(i,0,n){
			if(i+(1<<(k-1))>=n)continue;
			st[k][i]=oper(st[k-1][i],st[k-1][i+(1<<(k-1))]);
		}
	}
	ll query(ll s, ll e){
		e++; //askgdsfjsa
		ll k=63-__builtin_clzll(e-s);
		return oper(st[k][s],st[k][e-(1<<k)]);
	}
};
ST qs[2][MAXN];
ll h[2][MAXN][MAXN]; // 0 normal, 1 reversed  left,right

ll rect(ll l, ll r, ll p){
	ll iz=qs[0][p].query(l,r);
	ll dr=n-1-qs[1][n-1-p].query(l,r);
	//cout<<l<<","<<r<<" "<<p<<": "<<iz<<" "<<dr<<": "<<max((ll)0,dr-iz-1)<<"\n";
	//cout<<qs[1][n-1-p].query(l,r)<<"\n";
	//fore(i,0,n)cout<<qs[1][n-1-p].st[0][i]<<" ";
	//cout<<"\n\n";
	return max((ll)0,dr-iz-1);
}

ll dp[MAXN][MAXN];
ll f(ll l, ll r, ll p){
	ll &res=dp[l][r];
	if(res!=-1)return res;
	res=0;
	if(l)res=rect(l-1,r,p)+f(l-1,r,p);
	if(r<n-1)res=max(res,rect(l,r+1,p)+f(l,r+1,p));
	/*if(p==3){
		cout<<l<<","<<r<<": "<<res<<"\n";
	}*/
	return res;
}
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
	n=N;
	fore(i,0,n)fore(j,0,n){
		a[i][j]=F[i][j];
		b[i][n-1-j]=a[i][j];
	}
	mset(h,-1);
	fore(i,0,n){
		h[0][i][0]=(a[i][0]?0:-1);
		h[1][i][0]=(b[i][0]?0:-1);
		fore(j,1,n){
			if(a[i][j])h[0][i][j]=j;
			else h[0][i][j]=h[0][i][j-1];
			
			if(b[i][j])h[1][i][j]=j;
			else h[1][i][j]=h[1][i][j-1];
		}
	}
	/*fore(i,0,n){
		fore(j,0,n)cout<<a[i][j]<<" ";
		cout<<"\n";
	}
	cout<<"\n";
	fore(i,0,n){
		fore(j,0,n)cout<<b[i][j]<<" ";
		cout<<"\n";
	}
	cout<<"\n";
	fore(k,0,2){
		fore(i,0,n){
			fore(j,0,n)cout<<h[k][i][j]<<" ";
			cout<<"\n";
		}
		cout<<"\n";
	}*/
	
	fore(k,0,2)fore(j,0,n){
		vector<ll>v;
		fore(i,0,n)v.pb(h[k][i][j]);
		qs[k][j].init(v);
	}
	ll res=0;
	fore(p,0,n){
		mset(dp,-1);
		fore(i,0,n)res=max(res,f(i+1,i,p));
	}
	return res;
}

• 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