#include "soccer.h"
#include<bits/stdc++.h>
using namespace std;
int dp[8000006];
int biggest_stadium(int N, vector<vector<int>> F) {
memset(dp, -1, sizeof dp);
int n = N;
vector<vector<int>> a = F, next(n, vector<int>(n)), sum(n, vector<int>(n));
map<vector<int>, int> mp;
function<int(int, int, int, int)> summ = [&] (int l, int r, int x, int y) {
long long ans = sum[y][r];
if (x - 1 >= 0) ans -= sum[x - 1][r];
if (l - 1 >= 0) ans -= sum[y][l - 1];
if (x - 1 >= 0 && l - 1 >= 0) ans += sum[x - 1][l - 1];
return ans;
};
int cnt = 0;
function<int(int, int, int, int)> f = [&] (int l, int r, int x, int y) {
if (mp.count({l, r, x, y}) == 0) mp[{l, r, x, y}] = ++ cnt;
int ans = 0, id = mp[{l, r, x, y}];
if (dp[id] != -1) return dp[id];
if (x - 1 >= 0) {
for (int j = l; j <= r; j ++) {
if (a[x - 1][j]) continue;
int z = min(r, next[x - 1][j]);
int ll = 0, rr = x, mid;
while (ll < rr) {
mid = (ll + rr) / 2;
if (summ(j, z, mid, y) == 0) rr = mid;
else ll = mid + 1;
}
ans = max(ans, f(j, z, ll, y) + (z - j + 1) * (x - ll));
j = z;
}
}
if (y + 1 < n) {
for (int j = l; j <= r; j ++) {
if (a[y + 1][j]) continue;
int z = min(r, next[y + 1][j]);
int ll = y + 1, rr = n, mid;
while (ll < rr) {
mid = (ll + rr) / 2;
if (summ(j, z, x, mid) == 0) ll = mid + 1;
else rr = mid;
}
ll --;
ans = max(ans, f(j, z, x, ll) + (z - j + 1) * (ll - y));
j = z;
}
}
return dp[id] = ans;
};
for (int i = 0; i < n; i ++) {
for (int j = 0; j < n; j ++) {
sum[i][j] += a[i][j];
if (j) sum[i][j] += sum[i][j - 1];
}
}
for (int i = 1; i < n; i ++) {
for (int j = 0; j < n; j ++) sum[i][j] += sum[i - 1][j];
}
for (int i = 0; i < n; i ++) {
if (a[i][n - 1] == 0) next[i][n - 1] = n - 1;
else next[i][n - 1] = n - 2;
for (int j = n - 2; j >= 0; j --) {
if (a[i][j]) next[i][j] = j - 1;
else next[i][j] = next[i][j + 1];
}
}
int ans = 0;
for (int i = 0; i < n; i ++) {
for (int j = 0; j < n; j ++) {
if (a[i][j]) continue;
int ll = i, rr = n, mid, x, y;
while (ll < rr) {
mid = (ll + rr) / 2;
if (summ(j, next[i][j], i, mid) == 0) ll = mid + 1;
else rr = mid;
}
ll --;
y = ll;
ll = 0, rr = i;
while (ll < rr) {
mid = (ll + rr) / 2;
if (summ(j, next[i][j], mid, i) == 0) rr = mid;
else ll = mid + 1;
}
x = ll;
ans = max(ans, f(j, next[i][j], x, y) + (next[i][j] - j + 1) * (y - x + 1));
j = next[i][j];
}
}
return ans;
}
/*
3
0 0 0
0 1 0
0 0 0
*/
