#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using State = array<int,4>;
constexpr int NN = 2000;
template<>
struct std::hash<State> {
size_t operator()(State const& a) const {
return a[0]+NN*a[1]+1ll*NN*NN*a[2]+1ll*NN*NN*NN*a[3];
}
};
int r2(int x) {
return (31-__builtin_clz(x));
}
struct ST {
int mx;
array<vector<int>,11> data;
ST() {}
ST(vector<int> v, int _mx) : mx(_mx) {
int n = v.size();
data[0] = v;
int w = 1;
for (int i = 1; i < 11; ++i) {
w *= 2;
if (w > n) break;
data[i].resize(n+1-w);
for (int j = 0; j < n+1-w; ++j) {
data[i][j] = min(data[i-1][j],data[i-1][j+w/2]);
}
}
}
int query(int l, int r) {
if (l == r) return mx;
int sz = r2(r-l);
return min(data[sz][l],data[sz][r-(1<<sz)]);
}
};
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
vector<int> row(N,0);
vector<ST> up(N+1),down(N+1);
for (int x = 0; x < N; ++x) {
up[x] = ST(row,x);
for (int y = 0; y < N; ++y) {
row[y] = F[x][y] ? 0 : row[y]+1;
}
}
up[N] = ST(row,N);
fill(row.begin(),row.end(),0);
down[N] = ST(row,0);
for (int x = N-1; x >= 0; --x) {
for (int y = 0; y < N; ++y) {
row[y] = F[x][y] ? 0 : row[y]+1;
}
down[x] = ST(row,N-x);
}
vector<vector<int>> right(N,vector<int>(N+1));
for (int x = 0; x < N; ++x) {
right[x][N] = 1;
for (int y = N-1; y >= 0; --y) {
right[x][y] = F[x][y] ? 1 : right[x][y+1]+1;
}
}
// {-l,r,u,d}
unordered_map<State,int> dp;
// {-l,r,u,d}
priority_queue<State> pq;
for (int x = 0; x <= N; ++x) {
pq.push({-0,N,x,x});
}
int ans = 0;
while (!pq.empty()) {
auto t = pq.top(); pq.pop();
ans = max(ans,dp[t]);
auto [l,r,u,d] = t;
l *= -1;
if (u > 0) {
int nl = l;
while (true) {
int nr = min(r,nl+right[u-1][nl]-1);
int nu = u-up[u].query(nl,nr);
int nd = d+down[d].query(nl,nr);
State s = {-nl,nr,nu,nd};
if (!dp.count(s)) {
pq.push(s);
}
dp[s] = max(dp[s],dp[t]+(nr-nl)*(nd-d+u-nu));
nl = nr+1;
if (nl > r) break;
}
}
if (d < N) {
int nl = l;
while (true) {
int nr = min(r,nl+right[d][nl]-1);
int nu = u-up[u].query(nl,nr);
int nd = d+down[d].query(nl,nr);
State s = {-nl,nr,nu,nd};
if (!dp.count(s)) {
pq.push(s);
}
dp[s] = max(dp[s],dp[t]+(nr-nl)*(nd-d+u-nu));
nl = nr+1;
if (nl > r) break;
}
}
}
return ans;
}
