Submission #1235509

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235509		k1r1t0	Soccer Stadium (IOI23_soccer)	C++20	64 / 100	1884 ms	1007776 KiB

soccer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 510;

short ly[N][N][N], ry[N][N][N];
bool a[N][N];
int s[N][N], dp[N][N][N], m;

int biggest_stadium(int n, vector<vector<int>> f) {
	for (int i = 1; i <= n; i++)
	for (int j = 1; j <= n; j++)
		a[i][j] = f[i - 1][j - 1];
	for (int i = 1; i <= n; i++)
	for (int j = 1; j <= n; j++)
		s[i][j] = s[i][j - 1] + a[i][j];
	for (int i = 1; i <= n; i++)
	for (int l = 1; l <= n; l++)
	for (int r = l; r <= n; r++)
		ly[i][l][r] = ry[i][l][r] = -1;
	for (int l = 1; l <= n; l++)
	for (int r = n; r >= l; r--) {
		int ptr = 1;
		while (ptr <= n) {
			if (s[ptr][r] - s[ptr][l - 1] > 0) {
				ptr++;
				continue;
			}
			int last = ptr;
			while (last <= n && s[last][r] - s[last][l - 1] == 0)
				last++;
			for (int i = ptr; i < last; i++) {
				ly[i][l][r] = ptr;
				ry[i][l][r] = last - 1;
			}
			ptr = last;
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++)
	for (int l = 1; l <= n; l++)
	for (int r = n; r >= 1; r--)
		if (ly[i][l][r] >= 0) {
			int u = ly[i][l][r];
			int v = ry[i][l][r];
			dp[i][l][r] = max(dp[i][l][r], (v - u + 1) * (r - l + 1));
			ans = max(ans, dp[i][l][r]);
			if (l < r) {
				int nu = ly[i][l + 1][r];
				int nv = ry[i][l + 1][r];
				dp[i][l + 1][r] = max(dp[i][l + 1][r], dp[i][l][r] + (nv - v + u - nu) * (r - l));
				nu = ly[i][l][r - 1];
				nv = ry[i][l][r - 1];
				dp[i][l][r - 1] = max(dp[i][l][r - 1], dp[i][l][r] + (nv - v + u - nu) * (r - l));
			}
		}
	return ans;
}














/*
int main()
{
    int N;
    assert(1 == scanf("%d", &N));
    std::vector<std::vector<int>> F(N, std::vector<int>(N));
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            assert(1 == scanf("%d", &F[i][j]));
        }
    }
    fclose(stdin);

    int res = biggest_stadium(N, F);

    printf("%d\n", res);
    fclose(stdout);
    return 0;
}
//*/

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