#include "soccer.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <map>
typedef long long llong;
const int MAXN = 2000 + 10;
const int INF = 1e9;
int n;
int p[MAXN][MAXN];
int t[MAXN][MAXN];
inline int sum(int rowB, int colB, int rowE, int colE)
{
return p[rowE][colE] - p[rowB - 1][colE] - p[rowE][colB - 1] + p[rowB - 1][colB - 1];
}
std::pair <int,int> extend(int row, int colB, int colE)
{
assert(row > 0);
std::pair <int,int> sol;
int l = 0, r = row, mid;
while (l < r - 1)
{
mid = l + r >> 1;
if (sum(mid, colB, row, colE) != 0) l = mid;
else r = mid;
}
sol.first = r;
l = row, r = n + 1, mid;
while (l < r - 1)
{
mid = l + r >> 1;
if (sum(row, colB, mid, colE) == 0) l = mid;
else r = mid;
}
sol.second = l;
return sol;
}
std::vector <std::pair <int,int>> split(int row, int colB, int colE)
{
int last = colB;
std::vector <std::pair <int,int>> sol;
for (int i = colB ; i <= colE ; ++i)
{
if (t[row][i])
{
if (last < i)
{
sol.push_back({last, i - 1});
}
last = i + 1;
}
}
if (last <= colE) sol.push_back({last, colE});
return sol;
}
std::map <std::array <int,4>, int> dp;
int f(int rowB, int colB, int rowE, int colE)
{
if (colB > colE)
{
return 0;
}
if (rowB == 1 && rowE == n)
{
return 0;
}
if (dp.count({rowB, colB, rowE, colE}))
{
return dp[{rowB, colB, rowE, colE}];
}
int res = 0;
if (rowB > 1)
{
std::vector <std::pair <int,int>> v = split(rowB - 1, colB, colE);
for (const auto &[nextColB, nextColE] : v)
{
int lastRes = res;
auto [nextRowB, nextRowE] = extend(rowB - 1, nextColB, nextColE);
res = std::max(res, (nextColE - nextColB + 1) * (nextRowE - nextRowB + 1 - (rowE - rowB + 1)) + f(nextRowB, nextColB, nextRowE, nextColE));
}
}
if (rowE < n)
{
std::vector <std::pair <int,int>> v = split(rowE + 1, colB, colE);
for (const auto &[nextColB, nextColE] : v)
{
int lastRes = res;
auto [nextRowB, nextRowE] = extend(rowE + 1, nextColB, nextColE);
res = std::max(res, (nextColE - nextColB + 1) * (nextRowE - nextRowB + 1 - (rowE - rowB + 1)) + f(nextRowB, nextColB, nextRowE, nextColE));
}
}
return dp[{rowB, colB, rowE, colE}] = res;
}
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
n = N;
for (int i = 1 ; i <= n ; ++i)
{
for (int j = 1 ; j <= n ; ++j)
{
t[i][j] = F[i - 1][j - 1];
p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + t[i][j];
}
}
int max = 0;
for (int row = 1 ; row <= n ; ++row)
{
std::vector <std::pair <int,int>> v = split(row, 1, n);
for (const auto &[colB, colE] : v)
{
auto [rowB, rowE] = extend(row, colB, colE);
max = std::max(max, f(rowB, colB, rowE, colE) + (rowE - rowB + 1) * (colE - colB + 1));
}
}
return max;
}
