#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2005;
int U[MAX_N][MAX_N];
int D[MAX_N][MAX_N];
int segUmin[MAX_N][MAX_N];
int segDmin[MAX_N][MAX_N];
int dp[MAX_N][MAX_N];
int biggest_stadium(int N, std::vector<std::vector<int>> F) {
int cnt = 0;
for(vector<int> &row : F) {
for(int cell : row) {
cnt += cell;
}
}
if(cnt == 0) { return N*N; }
else if(cnt == 1) {
for(int r = 0; r < N; r ++) {
for(int c = 0; c < N; c ++) {
if(F[r][c]) {
r = min(r+1,N-r);
c = min(c+1,N-c);
return N*N-r*c;
}
}
}
}
if(N > 500) {
for(int r = 0; r < N; r ++) {
int lst = 1;
int switches = 0;
for(int c = 0; c < N; c ++) {
switches += lst^F[r][c];
lst = F[r][c];
}
switches += lst^1;
if(switches > 2) {
return MAX_N*MAX_N;
}
}
for(int c = 0; c < N; c ++) {
int lst = 1;
int switches = 0;
for(int r = 0; r < N; r ++) {
switches += lst^F[r][c];
lst = F[r][c];
}
switches += lst^1;
if(switches > 2) {
return MAX_N*MAX_N;
}
}
vector<pair<int,int>> segs;
for(int r = 0; r < N; r ++) {
int st = N, en = 0;
for(int c = 0; c < N; c ++) {
if(!F[r][c]) {
st = min(st,c);
en = max(en,c);
}
}
if(st <= en) {
segs.push_back({st,-en});
}
}
sort(segs.begin(),segs.end());
for(int i = 0; i < (int)(segs.size())-1; i ++) {
if(segs[i].second > segs[i+1].second) { return MAX_N*MAX_N; }
}
return N*N-cnt;
}
for(int c = 0; c < N; c ++) {
int lst = -1;
for(int r = 0; r < N; r ++) {
if(F[r][c]) { lst = r; }
U[r][c] = r-lst;
}
lst = N;
for(int r = N-1; r >= 0; r--) {
D[r][c] = lst-r-1;
if(F[r][c]) { lst = r; }
}
}
int res = 0;
for(int r = 0; r < N; r ++) {
for(int i = 0; i < N; i ++) {
segUmin[i][i] = MAX_N;;
for(int j = i + 1; j <= N; j ++) {
segUmin[i][j] = min(segUmin[i][j-1],U[r][j-1]);
}
segDmin[i][i] = MAX_N;
for(int j = i + 1; j <= N; j ++) {
segDmin[i][j] = min(segDmin[i][j-1],D[r][j-1]);
}
}
for(int sz = 1; sz <= N; sz ++) {
for(int r = sz; r <= N; r ++) {
int l = r-sz;
int cur_h = segUmin[l][r] + segDmin[l][r];
dp[l][r] = max(dp[l][r-1],dp[l+1][r]) + cur_h;
}
}
res = max(res,dp[0][N]);
}
return res;
}
