#include "soccer.h"
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize ("Ofast")
const int MAXN = 2e3 + 25;
const int M = (1 << 30) - 1;
const int B = 1e5 + 4;
int n, a[MAXN][MAXN], pref[MAXN][MAXN], pre[MAXN][MAXN];
int sparse[MAXN][11][MAXN];
int query (int x1, int y1, int x2, int y2) {
return pref[x2][y2] - pref[x1 - 1][y2] - pref[x2][y1 - 1] + pref[x1 - 1][y1 - 1];
}
struct custom_hash {
size_t operator()(array <int, 4> x) const {
return ((x[0] + x[1] * B + x[2] * B * B + x[3] * B * B * B) % M + M) % M;
}
};
unordered_map <array <int, 4>, int, custom_hash> memo;
int query (int j, int l, int r) {
int x = __lg(r - l + 1);
return min(sparse[j][x][l], sparse[j][x][r - (1 << x) + 1]);
}
int get (int l, int r, int x, int y) {
int R = r;
int ans = r + 1;
while (l <= r) {
int mid = (l + r) / 2;
if (query(x, mid, R) < y) {
l = mid + 1;
} else {
r = mid - 1; ans = mid;
}
}
return ans;
}
int get2 (int l, int r, int x, int y) {
int L = l;
int ans = l - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (query(x, L, mid) < y) {
r = mid - 1;
} else {
l = mid + 1; ans = mid;
}
}
return ans;
}
int ans (int x, int y, int l, int r) {
if (memo.count({x, y, l, r})) {
return memo[{x, y, l, r}];
}
int ret = 0;
for (int i = l; i <= r; i++) {
if (x != 1 && !a[x - 1][i]) {
if (i > l && !a[x - 1][i - 1]) {
continue;
}
int j = min(r + 1, pre[x - 1][i]);
int g = get(1, x - 1, i, j);
int h = get2(y + 1, n, i, j);
ret = max(ret, (j - i) * (x - g + h - y) + ans(g, h, i, j - 1));
i = j;
}
}
for (int i = l; i <= r; i++) {
if (y != n && !a[y + 1][i]) {
if (i > l && !a[y + 1][i - 1]) {
continue;
}
int j = min(r + 1, pre[y + 1][i]);
int g = get(1, x - 1, i, j);
int h = get2(y + 1, n, i, j);
ret = max(ret, (j - i) * (x - g + h - y) + ans(g, h, i, j - 1));
i = j;
}
}
return memo[{x, y, l, r}] = ret;
}
int biggest_stadium (int _N, vector <vector <int>> _F) {
//start with explaining the 25% solution
n = _N;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
a[i][j] = _F[i - 1][j - 1];
pref[i][j] = a[i][j] + pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
}
}
for (int i = 1; i <= n; i++) {
int z = n + 1;
for (int j = n; j >= 1; j--) {
if (a[i][j]) {
z = j;
}
pre[i][j] = z;
}
}
for (int j = 1; j <= n; j++) {
for (int i = 1; i <= n; i++) {
sparse[j][0][i] = pre[i][j];
}
for (int k = 1; k < 11; k++) {
for (int i = 1; i + (1 << k) - 1 <= n; i++) {
sparse[j][k][i] = min(sparse[j][k - 1][i], sparse[j][k - 1][i + (1 << (k - 1))]);
}
}
}
int ret = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (a[i][j]) {
continue;
}
if (j > 1 && !a[i][j - 1]) {
continue;
}
ret = max(ret, (pre[i][j] - j) + ans(i, i, j, pre[i][j] - 1));
}
}
return ret;
}
