Submission #1177290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177290		alexander707070	축구 경기장 (IOI23_soccer)	C++20	70 / 100	4601 ms	161320 KiB

soccer

#include<bits/stdc++.h>

#define MAXN 2007
using namespace std;

int n,t[MAXN][MAXN],ans;
int pr0[MAXN][MAXN],pr1[MAXN][MAXN];

int pref[MAXN][MAXN];

int sumrect(int a,int b,int c,int d){
	return pref[c][d] - pref[a-1][d] - pref[c][b-1] + pref[a-1][b-1];
}

pair<int,int> findrect(int row,int s,int t){
	int l=0,r=row,tt;

	while(l+1<r){
		tt=(l+r)/2;
		if(sumrect(tt,s,row,t)==0){
			r=tt;
		}else{
			l=tt;
		}
	}

	int up=r;

	l=row; r=n+1;
	while(l+1<r){
		tt=(l+r)/2;
		if(sumrect(row,s,tt,t)==0){
			l=tt;
		}else{
			r=tt;
		}
	}

	int down=l;

	return {up,down};
}

/// maxarea if current maximal rectangle lies on row x and stop in col y
bool li[MAXN][MAXN];
int dp[MAXN][MAXN];

int height[MAXN][MAXN],from[MAXN][MAXN],to[MAXN][MAXN];
stack<int> st;

void calc_rectangles(int row){
	height[row][0]=height[row][n+1]=-1;

	for(int col=1;col<=n;col++){
		if(t[row][col]==1)height[row][col]=0;
		else height[row][col]=height[row-1][col]+1;	
	}

	while(!st.empty())st.pop();

	st.push(0);
	for(int col=1;col<=n;col++){
		while(!st.empty() and height[row][col]<=height[row][st.top()]){
			st.pop();
		}

		from[row][col]=st.top()+1;
		st.push(col);
	}

	while(!st.empty())st.pop();

	st.push(n+1);
	for(int col=n;col>=1;col--){
		while(!st.empty() and height[row][col]<=height[row][st.top()]){
			st.pop();
		}

		to[row][col]=st.top()-1;
		st.push(col);
	}
}

int ff(int row,int col){

	if(li[row][col])return dp[row][col];
	li[row][col]=true;

	int area=height[row][col] * (to[row][col] - from[row][col] + 1);
	int top=row-height[row][col];

	dp[row][col]=area;

	if(top>0){
		int endr=pr0[top][to[row][col]];

		while(endr>=from[row][col]){
			int endl=max(pr1[top][endr]+1,from[row][col]);

			auto rect=findrect(top,endl,endr);
			
			int coll=pr1[rect.first-1][endr];
			if(coll==0)coll=endr;

			dp[row][col] = max( dp[row][col] , ff(rect.second,coll) - (endr-endl+1) * height[row][col] + area);

			endr=pr0[top][pr1[top][endr]];
		}
	}

	if(row<n){
		int endr=pr0[row+1][to[row][col]];

		while(endr>=from[row][col]){
			int endl=max(pr1[row+1][endr]+1,from[row][col]);

			auto rect=findrect(row+1,endl,endr);
			
			int coll=pr1[rect.first-1][endr];
			if(coll==0)coll=endr;

			dp[row][col] = max( dp[row][col] , ff(rect.second,coll) - (endr-endl+1) * height[row][col] + area);

			endr=pr0[row+1][pr1[row+1][endr]];
		}
	}
	
	return dp[row][col];
}

int biggest_stadium(int N, vector< vector<int> > F){
	n=N;

	for(int i=1;i<=n;i++){
		for(int f=1;f<=n;f++){
			t[i][f]=F[i-1][f-1];

			pref[i][f]=t[i][f]+pref[i][f-1]+pref[i-1][f]-pref[i-1][f-1];
		}
	}

	for(int i=1;i<=n;i++){
		int s0=0,s1=0;
		for(int f=1;f<=n;f++){		
			if(t[i][f]==0)s0=f;
			else s1=f;

			pr0[i][f]=s0; pr1[i][f]=s1;
		}
	}

	for(int i=1;i<=n;i++)calc_rectangles(i);

	for(int i=1;i<=n;i++){
		for(int f=1;f<=n;f++){
			ans=max(ans,ff(i,f));
		}
	}

	return ans;
}

/*int main(){

	cout<<biggest_stadium(5, {{0, 0, 0, 0, 0},
		{1, 0, 0, 0, 0},
		{0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0},
		{0, 0, 1, 0, 0}})<<"\n";

	return 0;
}*/

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