Submission #1233569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233569		AMnu	Soccer Stadium (IOI23_soccer)	C++20	100 / 100	1601 ms	147036 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int MAXN = 2e3+5;

int N, ans;
int A[MAXN][MAXN], P[MAXN][MAXN];
map <ll,int> D;

bool exist(int xa,int xb,int ya,int yb) {
	return P[xb][yb] - P[xb][ya-1] - P[xa-1][yb] + P[xa-1][ya-1];
}

int enlarge(int x,int ya,int yb);

int solve(int xa,int xb,int ya,int yb) {
	ll S = (ll)xa<<33|(ll)xb<<22|(ll)ya<<11|(ll)yb;
	if (D.count(S)) return D[S];
	int res = 0;
	if (xa > 1) {
		for (int i=yb;i>=ya;i=A[xa-1][i]-1) {
			if (A[xa-1][i] == i) continue;
			int j = max(ya,A[xa-1][i]+1);
			res = max(res, enlarge(xa,j,i) - (xb-xa+1)*(i-j+1));
		}
	}
	if (xb < N) {
		for (int i=yb;i>=ya;i=A[xb+1][i]-1) {
			if (A[xb+1][i] == i) continue;
			int j = max(ya,A[xb+1][i]+1);
			res = max(res, enlarge(xa,j,i) - (xb-xa+1)*(i-j+1));
		}
	}
	return D[S] = res;
}

int enlarge(int x,int ya,int yb) {
	int xa=x, xb=x;
	int l=1, r=x-1;
	while (l<=r) {
		int mid = (l+r)/2;
		if (exist(mid,x,ya,yb)) {
			l = mid+1;
		}
		else {
			xa = mid;
			r = mid-1;
		}
	}
	l=x+1, r=N;
	while (l<=r) {
		int mid = (l+r)/2;
		if (exist(x,mid,ya,yb)) {
			r = mid-1;
		}
		else {
			xb = mid;
			l = mid+1;
		}
	}
	return solve(xa,xb,ya,yb) + (xb-xa+1)*(yb-ya+1);
}

int biggest_stadium(int n, vector<vector<int>> F) {
	N = n;
	for (int i=1;i<=N;i++) {
		for (int j=1;j<=N;j++) {
			P[i][j] = P[i-1][j]+P[i][j-1]-P[i-1][j-1]+F[i-1][j-1];
			if (F[i-1][j-1]) {
				A[i][j] = j;
			}
			else {
				A[i][j] = A[i][j-1];
			}
		}
	}
	for (int i=1;i<=N;i++) {
		for (int j=N;j>0;j=A[i][j]-1) {
			if (A[i][j] == j) continue;
			ans = max(ans,enlarge(i,A[i][j]+1,j));
		}
	}
	return ans;
}

• 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: 30 / 30