제출 #842739

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
842739		errorgorn	축구 경기장 (IOI23_soccer)	C++17	64 / 100	4576 ms	95776 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ii pair<int,int>
#define iii pair<ii,int>
#define fi first
#define se second
#define endl '\n'

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n;
int arr[2005][2005];

vector<ii> V;

vector<ii> L[2005],R[2005];
int memo[2005][2005];

void dfs(int x,vector<ii> v,int d){
	if (x==-1 || x==n) return;
	
	vector<ii> res;
	for (auto [l,r]:v){
		rep(y,l,r+1) if (arr[x][y]==0){
			if (!res.empty() && res.back().se+1==y) res.back().se++;
			else res.pub({y,y});
		}
	}
	
	for (auto it:res) V.pub(it);
	
	dfs(x+d,res,d);
}

signed biggest_stadium(signed N, std::vector<std::vector<signed>> F){
	n=N;
	rep(x,0,n) rep(y,0,n) arr[x][y]=F[x][y];
	
	int ans=0;
	rep(x,0,n){
		vector<ii> v;
		rep(y,0,n) if (arr[x][y]==0){
			if (!v.empty() && v.back().se+1==y) v.back().se++;
			else v.pub({y,y});
		}
		
		V=v;
		dfs(x-1,v,-1);
		dfs(x+1,v,1);
		
		sort(all(V),[](ii i,ii j){
			if ((i.se-i.fi)==(j.se-j.fi)) return i>j;
			else return i.se-i.fi<j.se-j.fi;
		});
		vector<iii> res;
		for (auto it:V){
			if (!res.empty() && res.back().fi==it) res.back().se++;
			else res.pub({it,1});
		}
		
		//for (auto it:res) cout<<it.fi.fi<<" "<<it.fi.se<<" "<<it.se<<endl;
		//cout<<endl;
		
		rep(x,0,n) L[x].clear(),R[x].clear();
		
		for (auto it:res){
			L[it.fi.fi].pub({it.fi.se,it.se});
			R[it.fi.se].pub({it.fi.fi,it.se});
		}
		
		rep(x,0,n+1) rep(y,x,n+1) memo[x][y]=0;
		rep(l,0,n+1) rep(x,0,n-l+1){
			int y=x+l;
			if (x!=0){
				int t=memo[x][y];
				for (auto it:L[x]) if (y<=it.fi) t+=(min(it.fi,y)-x+1)*it.se;
				memo[x-1][y]=max(memo[x-1][y],t);
			}
			if (y!=n){
				int t=memo[x][y];
				for (auto it:R[y]) if (it.fi<=x) t+=(y-max(it.fi,x)+1)*it.se;
				memo[x][y+1]=max(memo[x][y+1],t);
			}
		}
		
		ans=max(ans,memo[0][n]);
		//rep(x,0,n+1){
			//rep(y,0,n+1) cout<<memo[x][y]<<" "; cout<<endl;
		//}
		//cout<<endl;
	}
	
	return ans;
}

• 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