Submission #1060258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060258		qilby	Soccer Stadium (IOI23_soccer)	C++17	100 / 100	1219 ms	170064 KiB

soccer

#include <bits/stdc++.h>

#include "soccer.h"

using namespace std;

const int N = 2009;

map < array < int , 4 > , int > f;
int n, a[N][N], p[N][N], nxt[N][N];

int calc(int li, int ri, int lj, int rj) {
	int l = 1, r = li;

	while (l < r) {
		int mid = (l + r) >> 1;
		if (p[li][rj] - p[li][lj - 1] - p[mid - 1][rj] + p[mid - 1][lj - 1] < 1) r = mid;
		else l = mid + 1;
	}

	if (l < li) return calc(l, ri, lj, rj) + (rj - lj + 1) * (li - l);

	l = ri, r = n;

	while (l < r) {
		int mid = (l + r + 1) >> 1;
		if (p[mid][rj] - p[mid][lj - 1] - p[ri - 1][rj] + p[ri - 1][lj - 1] < 1) l = mid;
		else r = mid - 1;
	}

	if (l > ri) return calc(li, l, lj, rj) + (rj - lj + 1) * (l - ri);

	if (f.count({li, ri, lj, rj})) return f[{li, ri, lj, rj}];

	int crr = 0;

	if (li > 1) {
		for (int j = lj - 1; j < rj; j = nxt[li - 1][j + 1]) {
			if (a[li - 1][j + 1]) continue;
			int l = j + 1, r = min(rj, nxt[li - 1][j + 1] - 1);
			if (l <= r) crr = max(crr, calc(li - 1, ri, l, r) + r - l + 1);
		}
	}

	if (ri < n) {
		for (int j = lj - 1; j < rj; j = nxt[ri + 1][j + 1]) {
			if (a[ri + 1][j + 1]) continue;
			int l = j + 1, r = min(rj, nxt[ri + 1][j + 1] - 1);
			if (l <= r) crr = max(crr, calc(li, ri + 1, l, r) + r - l + 1);
		}
	}

	f[{li, ri, lj, rj}] = crr;

	return crr;
}

int biggest_stadium(int N, vector < vector < int > > w) {
	n = N;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			a[i][j] = w[i - 1][j - 1];
			p[i][j] = p[i][j - 1] + p[i - 1][j] - p[i - 1][j - 1] + a[i][j];
		}
	}

	for (int i = 1; i <= n; i++) {
		nxt[i][n + 1] = n + 1;

		for (int j = n; j >= 1; j--) {
			if (a[i][j]) nxt[i][j] = j;
			else nxt[i][j] = nxt[i][j + 1];
		}
	}

	int res = 0;

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < n; j++) {
			if ((!j || a[i][j]) && !a[i][j + 1]) {
				res = max(res, calc(i, i, j + 1, nxt[i][j + 1] - 1) + nxt[i][j + 1] - j - 1);
			}
		}
	}

	return res;
}

• 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