#include "soccer.h"
// #include "Debug.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2020;
map<int, int> f[N][N];
int isBad(vector<pair<int, int>> a)
{
int len = size(a);
for (int i = 0; i < len; i++)
for (int j = i + 1; j < len; j++)
{
auto [l, r] = a[i];
auto [ll, rr] = a[j];
int intersect = min(r, rr) - max(l, ll);
if (intersect >= 0 && intersect < min(r - l, rr - ll))
return 1;
}
return 0;
}
int biggest_stadium(int n, std::vector<std::vector<int>> a)
{
int area = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
area += 1 - a[i][j];
if (area == n * n - 1)
{
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (a[i][j])
{
int exclude = min(i + 1, n - i) * min(j + 1, n - j);
return n * n - exclude;
}
}
int canUseAll = 1;
vector<vector<pair<int, int>>> rows(n);
vector<pair<int, int>> allRows;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n;)
if (a[i][j]) j++;
else
{
int jj = j + 1;
while (jj < n && !a[i][jj])
jj++;
rows[i].push_back({j, jj - 1});
j = jj;
}
if (size(rows[i]) > 1) canUseAll = 0;
else if (size(rows[i]) == 1) allRows.push_back(rows[i][0]);
}
vector<vector<pair<int, int>>> cols(n);
vector<pair<int, int>> allCols;
for (int j = 0; j < n; j++)
{
for (int i = 0; i < n;)
if (a[i][j]) i++;
else
{
int ii = i + 1;
while (ii < n && !a[ii][j])
ii++;
cols[j].push_back({i, ii - 1});
i = ii;
}
if (size(cols[j]) > 1) canUseAll = 0;
else if (size(cols[j]) == 1) allCols.push_back(cols[j][0]);
}
canUseAll &= !isBad(allRows) && !isBad(allCols);
if (canUseAll)
return area;
for (int i = 0; i < n; i++)
for (auto [l, r] : rows[i])
f[i][i][l * N + r] = r - l + 1;
int ans = 0;
for (int len = 1; len < n; len++)
for (int i = 0; i + len <= n; i++)
{
int ii = i + len - 1;
for (auto [u, v] : f[i][ii])
{
int j = u / N, jj = u % N;
ans = max(ans, v);
if (i)
{
for (auto [l, r] : rows[i - 1])
{
int k = max(j, l), kk = min(jj, r);
int uu = k * N + kk;
if (k <= kk)
f[i - 1][ii][uu] = max(f[i - 1][ii][uu], v + kk - k + 1);
}
}
if (ii + 1 < n)
{
for (auto [l, r] : rows[ii + 1])
{
int k = max(j, l), kk = min(jj, r);
int uu = k * N + kk;
if (k <= kk)
f[i][ii + 1][uu] = max(f[i][ii + 1][uu], v + kk - k + 1);
}
}
}
}
for (auto [_, v] : f[0][n - 1])
ans = max(ans, v);
return ans;
}
