#include "soccer.h"
#include <bits/stdc++.h>
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define pb push_back
#define eb emplace_back
#define fst first
#define snd second
using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
using ll = long long;
const int MAX_N = 2005;
int pref[MAX_N][MAX_N], n;
vector<ii> ran[MAX_N];
int query(int i1, int i2, int j1, int j2) {
i2++, j2++;
return pref[i2][j2] - pref[i1][j2] - pref[i2][j1] + pref[i1][j1];
}
ii getMaximal(int i, int l, int r) {
int lo = i, hi = n;
while (hi - lo > 1) {
int mid = (lo + hi) / 2;
if (query(i, mid, l, r) == 0) lo = mid;
else hi = mid;
}
int i2 = lo;
lo = -1, hi = i;
while (hi - lo > 1) {
int mid = (lo + hi) / 2;
if (query(mid, i, l, r) == 0) hi = mid;
else lo = mid;
}
int i1 = hi;
return ii{i1, i2};
}
vector<ii> getRanges(int i, int l, int r) {
int lo = -1, hi = sz(ran[i]);
while (hi - lo > 1) {
int mid = (lo + hi) / 2;
if (ran[i][mid].snd >= l) hi = mid;
else lo = mid;
}
int j = hi;
vector<ii> ret;
while (j < sz(ran[i]) && ran[i][j].fst <= r) {
ret.eb(max(ran[i][j].fst, l), min(ran[i][j].snd, r));
j++;
}
return ret;
}
map<int, int> memo[MAX_N][MAX_N];
int dp(int i, int i1, int i2, int j1, int j2) {
if (memo[j1][j2].count(i)) return memo[j1][j2][i];
int &ret = memo[j1][j2][i];
if (i1 > 0) for (auto [b1, b2] : getRanges(i1 - 1, j1, j2)) {
auto [a1, a2] = getMaximal(i1 - 1, b1, b2);
ret = max(ret, dp(i1 - 1, a1, a2, b1, b2) + (b2 - b1 + 1) * ((a2 - a1 + 1) - (i2 - i1 + 1)));
}
if (i2 + 1 < n) for (auto [b1, b2] : getRanges(i2 + 1, j1, j2)) {
auto [a1, a2] = getMaximal(i2 + 1, b1, b2);
ret = max(ret, dp(i2 + 1, a1, a2, b1, b2) + (b2 - b1 + 1) * ((a2 - a1 + 1) - (i2 - i1 + 1)));
}
return ret;
}
int biggest_stadium(int N, vector<vi> F) {
n = N;
forn(i, n) forn(j, n) pref[i + 1][j + 1] = pref[i][j + 1] + pref[i + 1][j] - pref[i][j] + F[i][j];
forn(i, n) {
forn(j, n) {
if (F[i][j]) continue;
if (j == 0 || F[i][j - 1]) {
ran[i].eb(j, j);
} else {
ran[i].back().snd++;
}
}
}
int ret = 0;
forn(i, n) for (auto [j1, j2] : ran[i]) {
auto [i1, i2] = getMaximal(i, j1, j2);
ret = max(ret, dp(i, i1, i2, j1, j2) + (j2 - j1 + 1) * (i2 - i1 + 1));
}
return ret;
}
