#include "soccer.h"
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
int top[2005][2005];
int bottom[2005][2005];
int rangetop[2005][2005], rangebottom[2005][2005];
int f[2005][2005];
const int inf = -100000000;
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
int trees = 0, x = 0, y = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (F[i][j]) {
trees++;
x = i; y = j;
}
}
}
if (trees == 0) {
return N * N;
}
if (trees == 1) {
return N * N - min(x+1, N-x) * min(y+1, N-y);
}
int widest_row = -1;
int widest_cnt = 0;
for (int i = 0; i < N; i++) {
int emptycnt = 0;
for (int j = 0; j < N; j++) {
if (F[i][j]) {
top[i][j] = N;
} else if (i == 0 || F[i-1][j]) {
top[i][j] = i; emptycnt++;
} else {
top[i][j] = top[i-1][j]; emptycnt++;
}
}
if (emptycnt >= widest_cnt) {
widest_row = i;
widest_cnt = emptycnt;
}
}
for (int i = N - 1; i >= 0; i--) {
for (int j = 0; j < N; j++) {
if (F[i][j]) {
bottom[i][j] = -1;
} else if (i == N - 1 || F[i+1][j]) {
bottom[i][j] = i;
} else {
bottom[i][j] = bottom[i+1][j];
}
}
}
int ans = 0;
for (int mrow = 0; mrow < N; mrow++) {
if (N > 500 && mrow != widest_row) continue;
for (int i = 0; i < N; i++) {
rangetop[i][i] = top[mrow][i];
rangebottom[i][i] = bottom[mrow][i];
f[i][i] = bottom[mrow][i] - top[mrow][i] + 1;
if (f[i][i] < 0) f[i][i] = -inf;
}
for (int siz = 2; siz <= N; siz++) {
for (int i = 0; i <= N - siz; i++) {
rangetop[i][i+siz-1] = max(rangetop[i+1][i+siz-1], top[mrow][i]);
rangebottom[i][i+siz-1] = min(rangebottom[i+1][i+siz-1], bottom[mrow][i]);
if (rangetop[i][i+siz-1] > rangebottom[i][i+siz-1]) {
f[i][i+siz-1] = -inf;
} else {
f[i][i+siz-1] = max(f[i+1][i+siz-1], f[i][i+siz-2]) + rangebottom[i][i+siz-1] - rangetop[i][i+siz-1] + 1;
ans = max(ans, f[i][i+siz-1]);
}
}
}
}
return ans;
}
