Submission #1240051

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240051		vako_p	Soccer Stadium (IOI23_soccer)	C++20	25 / 100	294 ms	186164 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],mx[2][mxN],L[2][mxN][mxN],R[2][mxN][mxN];

int biggest_stadium(int N, std::vector<std::vector<int>> F){
	n = N;
	ll sum = 0;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			a[i + 1][j + 1] = 1 - F[i][j];
			sum += 1 - F[i][j];
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			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 sum;
}

• 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