제출 #1177158

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1177158		alexander707070	축구 경기장 (IOI23_soccer)	C++20	48 / 100	4595 ms	14668 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 dp[37][37][37][37];

void calcdp(){
	for(int len=n;len>=1;len--){
		for(int up=1;up+len-1<=n;up++){
			int down=up+len-1;

			for(int len2=1;len2<=n;len2++){
				for(int l=1;l+len2-1<=n;l++){
					int r=l+len2-1;

					if(up>1){
						int pos=pr0[up-1][r];

						while(pos>=l){
							int from=max(l,pr1[up-1][pos]+1);
							dp[up][down][l][r]=max(dp[up][down][l][r] , dp[up-1][down][from][pos] + pos-from+1);

							pos=pr0[up-1][pr1[up-1][pos]];
						}
					}

					if(down<n){
						int pos=pr0[down+1][r];
						
						while(pos>=l){
							int from=max(l,pr1[down+1][pos]+1);
							dp[up][down][l][r]=max(dp[up][down][l][r] , dp[up][down+1][from][pos] + pos-from+1);

							pos=pr0[down+1][pr1[down+1][pos]];
						}
					}
				}
			}
		}
	}
}

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];
		}
	}

	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;
		}
	}

	calcdp();

	ans=0;
	for(int i=1;i<=n;i++){
		for(int f=1;f<=n;f++){
			if(t[i][f]==0 and (f==n or t[i][f+1]==1)){
				ans=max(ans,dp[i][i][pr1[i][f]+1][f] + f-pr1[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: 0 / 6
• Subtask 2: 8 / 8
• Subtask 3: 22 / 22
• Subtask 4: 18 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30