Submission #1240059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240059		vako_p	Soccer Stadium (IOI23_soccer)	C++20	8 / 100	3689 ms	620 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define sd second
#define debug(x) cerr << #x << " ------> " << x << endl;

const int mxN = 2005;
ll n,a[mxN][mxN],p[mxN][mxN],L[2][mxN][mxN],R[2][mxN][mxN];

bool check(){
	vector<vector<int>> mx(2, vector<int>(n + 5, 0));
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			L[0][i][j] = L[1][i][j] = R[0][i][j] = R[1][i][j] = 0;
			if(a[i][j]){
				mx[0][i] = j;
				mx[1][j] = i;
			}
			p[i][j] = a[i][j] + p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			if(!a[i][j]) continue;
			if(a[i][j - 1]) L[0][i][j] = L[0][i][j - 1];
			else L[0][i][j] = j;
			if(a[i - 1][j]) L[1][i][j] = L[1][i - 1][j];
			else L[1][i][j] = i;
		}
	}
	for(int i = n; i >= 1; i--){
		for(int j = n; j >= 1; j--){
			if(!a[i][j]) continue;
			if(a[i][j + 1]) R[0][i][j] = R[0][i][j + 1];
			else{
				R[0][i][j] = j;
				if(mx[0][i] > j) return 0;
			}
			if(a[i + 1][j]) R[1][i][j] = R[1][i + 1][j];
			else{
				R[1][i][j] = i;
				if(mx[1][j] > i) return 0;
			}
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			if(!a[i][j]) continue;
			if(p[L[1][i][j] - 1][L[0][i][j] - 1]) return 0;
			if(p[L[1][i][j] - 1][n] - p[L[1][i][j] - 1][R[0][i][j]]) return 0;
			if(p[n][L[0][i][j] - 1] - p[R[1][i][j]][L[0][i][j] - 1]) return 0;
			if(p[n][n] + p[R[1][i][j]][R[0][i][j]] - p[n][R[0][i][j]] - p[R[1][i][j]][n]) return 0;
		}
	}
	return true;
}

int biggest_stadium(int N, std::vector<std::vector<int>> F){
	n = N;
	int ans = 0;
	for(int bit = 1; bit < (1 << (n * n)); bit++){
		for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) a[i][j] = 0;
		bool ok = true;
		for(int i = 0; i < n * n; i++){
			if((1 << i) & bit and F[i / n][i % n]){
				ok = false;
				break;
			}
			if((1 << i) & bit) a[i / n + 1][i % n + 1] = 1; 
		}
		if(ok and check()) ans = max(ans, __builtin_popcount(bit));
	}
	return ans;
}

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