Submission #1235506

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235506		k1r1t0	Soccer Stadium (IOI23_soccer)	C++20	48 / 100	161 ms	147472 KiB

soccer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 510;

short t[N][N][N];
bool a[N][N];
vector<array<short, 4>> rect;
vector<int> dp;
int s[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 l = 1; l <= n; l++)
	for (int r = l; r <= n; r++)
	for (int i = 1; i <= n; i++)
		t[l][r][i] = -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++)
				t[l][r][i] = rect.size();
			rect.push_back({l, r, ptr, last - 1});
			ptr = last;
		}
	}
	m = rect.size();
	dp = vector<int>(m);
	for (int i = 0; i < m; i++)
		dp[i] = (rect[i][1] - rect[i][0] + 1) * (rect[i][3] - rect[i][2] + 1);
	for (int i = 0; i < m; i++) {
		auto [lx, rx, ly, ry] = rect[i];
		if (lx + 1 <= rx) {
			int j = t[lx + 1][rx][ly];
			auto [nlx, nrx, nly, nry] = rect[j];
			dp[j] = max(dp[j], dp[i] + (nrx - nlx + 1) * (nry - ry + ly - nly));
		}
		if (lx <= rx - 1) {
			int j = t[lx][rx - 1][ly];
			auto [nlx, nrx, nly, nry] = rect[j];
			dp[j] = max(dp[j], dp[i] + (nrx - nlx + 1) * (nry - ry + ly - nly));
		}
	}
	int ans = 0;
	for (int i = 0; i < m; i++)
		ans = max(ans, dp[i]);
	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;
}
//*/

Compilation message (stderr)

soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:38:41: warning: narrowing conversion of 'l' from 'int' to 'short int' [-Wnarrowing]
   38 |                         rect.push_back({l, r, ptr, last - 1});
      |                                         ^
soccer.cpp:38:44: warning: narrowing conversion of 'r' from 'int' to 'short int' [-Wnarrowing]
   38 |                         rect.push_back({l, r, ptr, last - 1});
      |                                            ^
soccer.cpp:38:47: warning: narrowing conversion of 'ptr' from 'int' to 'short int' [-Wnarrowing]
   38 |                         rect.push_back({l, r, ptr, last - 1});
      |                                               ^~~
soccer.cpp:38:57: warning: narrowing conversion of '(last - 1)' from 'int' to 'short int' [-Wnarrowing]
   38 |                         rect.push_back({l, r, ptr, last - 1});
      |                                                    ~~~~~^~~

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