#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 2000;
map<int, int> dp[mxN][mxN];
int full(int N, vector<vector<int>> F) {
vector<vector<int>> sum(N, vector<int> (N, 0));
for(int i = 0; i < N; i ++) {
for(int j = 0; j < N; j ++) {
sum[i][j] = F[i][j];
if(i) sum[i][j] += sum[i - 1][j];
if(j) sum[i][j] += sum[i][j - 1];
if(i && j) sum[i][j] -= sum[i - 1][j - 1];
}
}
auto Area = [&] (int x, int y, int u, int v) {
return sum[u][v] - (x ? sum[x - 1][v] : 0) - (y ? sum[u][y - 1] : 0) + (x && y ? sum[x - 1][y - 1] : 0);
};
auto Range = [&] (int x, int L, int R) {
int low = x, high = x - 1;
for(int i = 10; i >= 0; i --) {
if(low - (1 << i) >= 0 && Area(low - (1 << i), L, x, R) == 0) low -= (1 << i);
if(high + (1 << i) < N && Area(x, L, high + (1 << i), R) == 0) high += (1 << i);
}
return make_pair(low, high);
};
function<int(int, int, int)> DP = [&] (int x, int L, int R) {
if(dp[L][R].count(x)) return dp[L][R][x];
auto [low, high] = Range(x, L, R);
if(x != low) return DP(low, L, R);
int ans = 0;
for(int i = L; i <= R; i ++) {
auto check = [&] (int r) {
return low - 1 >= 0 && Area(low - 1, i, low - 1, r) == 0;
};
if(check(i) == 0) continue ;
int j = i;
for(int k = 10; k >= 0; k --) if(j + (1 << k) <= R && check(j + (1 << k))) j += (1 << k);
auto [_low, _high] = Range(low - 1, i, j);
ans = max(ans, DP(_low, i, j) + (low - _low + _high - high) * (j - i + 1));
i = j;
}
for(int i = L; i <= R; i ++) {
auto check = [&] (int r) {
return high + 1 < N && Area(high + 1, i, high + 1, r) == 0;
};
if(check(i) == 0) continue ;
int j = i;
for(int k = 10; k >= 0; k --) if(j + (1 << k) <= R && check(j + (1 << k))) j += (1 << k);
auto [_low, _high] = Range(high + 1, i, j);
ans = max(ans, DP(_low, i, j) + (low - _low + _high - high) * (j - i + 1));
i = j;
}
return dp[L][R][x] = ans;
};
int result = 0;
for(int i = 0; i < N; i ++) {
pair<int, int> x = Range(i, 0, N - 1);
result = max(result, DP(i, 0, N - 1) + (x.second - x.first + 1) * N);
}
return result;
}
int biggest_stadium(int N, vector<vector<int>> F) {
return full(N, F);
}
