Submission #1132272

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132272		denniskim	Soccer Stadium (IOI23_soccer)	C++17	100 / 100	2333 ms	146972 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<int, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
const int MAXN = 2005;

int n;
map<array<int, 4>, int> mp;
vector<vector<int>> a;

int sum[MAXN][MAXN];

/// just chilling
vector<pi> get_interval(int r, int s, int e) {
	vector<pi> ans;
	for (int i = s; i <= e; i++) {
		if (a[r][i] == 1)
			continue;
		int j = i;
		while (j <= e && a[r][j] == 0)
			j++;
		ans.push_back({i, j - 1});
		i = j;
	}
	return ans;
}

int getsum(int i1, int i2, int j1, int j2) { return sum[i2 + 1][j2 + 1] - sum[i1][j2 + 1] - sum[i2 + 1][j1] + sum[i1][j1]; }
pi expand(int r, int u, int v) {
	pi ans;
	{
		int s = 0, e = r;
		while (s != e) {
			int m = (s + e) / 2;
			if (getsum(m, r, u, v) == 0)
				e = m;
			else
				s = m + 1;
		}
		ans[0] = s;
	}
	{
		int s = r, e = n - 1;
		while (s != e) {
			int m = (s + e + 1) / 2;
			if (getsum(r, m, u, v) == 0)
				s = m;
			else
				e = m - 1;
		}
		ans[1] = s;
	}
	return ans;
}

int f(int r1, int r2, int c1, int c2) {
	if (mp.count({r1, r2, c1, c2}))
		return mp[{r1, r2, c1, c2}];
	vector<pi> i1, i2;
	int ret = 0;
	if (r1 > 0) {
		auto intv = get_interval(r1 - 1, c1, c2);
		for (auto &[j1, j2] : intv) {
			auto [i1, i2] = expand(r1 - 1, j1, j2);
			ret = max(ret, f(i1, i2, j1, j2) + (i2 - i1 - (r2 - r1)) * (j2 - j1 + 1));
		}
	}
	if (r2 < n - 1) {
		auto intv = get_interval(r2 + 1, c1, c2);
		for (auto &[j1, j2] : intv) {
			auto [i1, i2] = expand(r2 + 1, j1, j2);
			ret = max(ret, f(i1, i2, j1, j2) + (i2 - i1 - (r2 - r1)) * (j2 - j1 + 1));
		}
	}
	return mp[{r1, r2, c1, c2}] = ret;
}

int biggest_stadium(int N, std::vector<std::vector<int>> F) {
	a = F;
	n = N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + F[i][j];
		}
	}
	int ret = 0;
	for (int i = 0; i < N; i++) {
		auto intv = get_interval(i, 0, N - 1);
		for (auto &[j1, j2] : intv) {
			auto [i1, i2] = expand(i, j1, j2);
			ret = max(ret, f(i1, i2, j1, j2) + (i2 - i1 + 1) * (j2 - j1 + 1));
		}
	}
	return ret;
}

• 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