Submission #1077449

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077449		emptypringlescan	Soccer Stadium (IOI23_soccer)	C++17	25 / 100	394 ms	165456 KiB

soccer

#include <bits/stdc++.h>
using namespace std;
int biggest_stadium(int n,vector<vector<int> > arr){
	int close[4][n][n];
	for(int j=0; j<n; j++){
		int prv=-1;
		for(int i=0; i<n; i++){
			if(arr[i][j]) prv=i;
			close[0][i][j]=prv;
		}
		prv=n;
		for(int i=n-1; i>=0; i--){
			if(arr[i][j]) prv=i;
			close[1][i][j]=prv;
		}
	}
	for(int i=0; i<n; i++){
		int prv=-1;
		for(int j=0; j<n; j++){
			if(arr[i][j]) prv=j;
			close[2][i][j]=prv;
		}
		prv=n;
		for(int j=n-1; j>=0; j--){
			if(arr[i][j]) prv=j;
			close[3][i][j]=prv;
		}
	}
	int pref[4][n+5][n+5];
	memset(pref,0,sizeof(pref));
	for(int i=0; i<n; i++) for(int j=0; j<n; j++) arr[i][j]^=1;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			pref[0][i+1][j+1]=pref[0][i+1][j]+pref[0][i][j+1]-pref[0][i][j]+arr[i][j];
		}
		for(int j=n-1; j>=0; j--){
			pref[1][i+1][j+1]=pref[1][i+1][j+2]+pref[1][i][j+1]-pref[1][i][j+2]+arr[i][j];
		}
	}
	for(int i=n-1; i>=0; i--){
		for(int j=0; j<n; j++){
			pref[2][i+1][j+1]=pref[2][i+1][j]+pref[2][i+2][j+1]-pref[2][i+2][j]+arr[i][j];
		}
		for(int j=n-1; j>=0; j--){
			pref[3][i+1][j+1]=pref[3][i+1][j+2]+pref[3][i+2][j+1]-pref[3][i+2][j+2]+arr[i][j];
		}
	}
	for(int a=1; a<=n; a++){
		for(int b=1; b<=n; b++){
			if(arr[a-1][b-1]==0){
				if((pref[0][a-1][b]-pref[0][a-1][b-1])&&(pref[2][a+1][b]-pref[2][a+1][b-1])) return 0;
				if((pref[0][a][b-1]-pref[0][a-1][b-1])&&(pref[3][a][b+1]-pref[3][a+1][b+1])) return 0;
				continue;
            }
			int u=close[0][a-1][b-1],d=close[1][a-1][b-1],l=close[2][a-1][b-1],r=close[3][a-1][b-1];
			//cout << a << ' ' << b << '\n';
			//cout << u << ' ' << d << ' ' << l << ' ' << r << '\n';
			if(pref[0][u+1][l+1]) return 0;
			if(pref[1][u+1][r+1]) return 0;
			if(pref[2][d+1][l+1]) return 0;
			if(pref[3][d+1][r+1]) return 0;
		}
	}
	return pref[0][n][n];
}

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