#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int dp[510][510][510];
vector<pair<int,int>> ran[510][510];
int large_case(int N, vector<vector<int>> F) {
vector<vector<int>> vis(N, vector<int>(N, 0));
queue<pair<int,int>> q;
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
if (F[i][j] == 0) {
vis[i][j] = 1;
q.push({i, j});
break;
}
}
if (!q.empty()) break;
}
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int k=0; k<4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
if (vis[nx][ny]) continue;
if (F[nx][ny]) continue;
vis[nx][ny] = 1;
q.push({nx, ny});
}
}
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
if (F[i][j] == 0 && vis[i][j] == 0) {
return 0;
}
}
}
int tot = 0;
bool flag = false;
int pl = -1, pr = -1;
vector<pair<int,int>> ran;
for (int i=0; i<N; i++) {
int l = -1, r = -1, cnt = 0;
for (int j=0; j<N; j++) {
if (F[i][j] == 0) {
if (l == -1) l = j;
r = j;
cnt ++;
}
}
if (cnt == 0) {
pl = -1; pr = -1;
continue;
}
ran.push_back({l, r});
if (r - l + 1 != cnt) {
return 0;
}
if (pl != -1) {
if (!flag) {
if (l <= pl && pr <= r) {}
else if (pl <= l && r <= pr) {
flag = true;
}
else return 0;
}
else {
if (pl <= l && r <= pr) {}
else return 0;
}
}
pl = l; pr = r;
tot += cnt;
}
sort(ran.begin(), ran.end(), [&](pair<int,int> &u, pair<int,int> &v) {
return u.second - u.first < v.second - v.first;
});
for (int i=0; i+1<ran.size(); i++) {
if (ran[i+1].first <= ran[i].first && ran[i].second <= ran[i+1].second) {}
else return 0;
}
return tot;
}
int biggest_stadium(int N, vector<vector<int>> F) {
int tot = 0;
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
if (F[i][j] == 1) {
tot ++;
}
}
}
if (tot == 0) return N * N;
if (tot == 1) {
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
if (F[i][j] == 1) {
return N * N - min(i+1, N-i) * min(j+1, N-j);
}
}
}
}
if (N > 500) {
return large_case(N, F);
}
for (int i=0; i<N; i++) {
vector<int> cnt(N, 0);
for (int j=i; j<N; j++) {
for (int k=0; k<N; k++) {
if (F[j][k] == 0) {
cnt[k] ++;
}
}
int l = -1;
for (int k=0; k<N; k++) {
if (cnt[k] == j-i+1) {
if (l == -1) l = k;
if (k == N-1 || cnt[k+1] != j-i+1) {
ran[i][j].push_back({l, k});
}
}
else l = -1;
}
}
}
int ans = 0;
for (int i=0; i<N; i++) {
for (int j=0; j<ran[i][i].size(); j++) {
dp[i][i][j] = ran[i][i][j].second - ran[i][i][j].first + 1;
ans = max(ans, dp[i][i][j]);
}
}
for (int d=1; d<=N-1; d++) {
for (int i=0; i<N-d; i++) {
int j = i + d;
int l = 0;
for (int k=0; k<ran[i][j].size(); k++) {
while (ran[i][j-1][l].second < ran[i][j][k].first)
l ++;
dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][l] + ran[i][j][k].second - ran[i][j][k].first + 1);
ans = max(ans, dp[i][j][k]);
}
l = 0;
for (int k=0; k<ran[i][j].size(); k++) {
while (ran[i+1][j][l].second < ran[i][j][k].first)
l ++;
dp[i][j][k] = max(dp[i][j][k], dp[i+1][j][l] + ran[i][j][k].second - ran[i][j][k].first + 1);
ans = max(ans, dp[i][j][k]);
}
}
}
return ans;
}
