#include <bits/stdc++.h>
#include "soccer.h"
using namespace std;
typedef long long ll;
ll tryCase(int n, vector<vector<int>> f) {
vector<pair<ll, ll>> v(n, {-1, -1}), h(n, {-1, -1});
ll num = 0;
bool done = false;
pair<ll, ll> prev = {-1, -1}, mn = {-1, -1};
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!f[i][j]) {
if (done)
return 0;
if (v[i].first == -1) v[i].first = j;
if (j - v[i].second > 1 && v[i].second != -1)
return 0;
v[i].second = j;
num++;
}
}
if (v[i].first == -1 && num > 0) done = true;
if (prev.first == -1) {
prev = v[i];
mn = v[i];
continue;
}
if (v[i].first == -1) continue;
if (v[i].first > mn.first && v[i].second > mn.second)
return 0;
if (v[i].first < mn.first && v[i].second < mn.second)
return 0;
mn.first = max(mn.first, v[i].first);
mn.second = min(mn.second, v[i].second);
if (v[i].first > prev.first && v[i].second > prev.second)
return 0;
if (v[i].first < prev.first && v[i].second < prev.second)
return 0;
prev = v[i];
}
if (num >= n*n-1) {
ll x = -1, y = -1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (f[i][j]) {
x = i;
y = j;
}
}
}
if (x == -1) return n*n;
ll mx = max({
x*n + y*n - x*y,
(n-1-x)*n + y*n - (n-1-x)*y,
x*n + (n-1-y)*n - x*(n-1-y),
(n-1-x)*n + (n-1-y)*n - (n-1-x)*(n-1-y),
});
return mx;
}
num = 0;
done = false;
prev = {-1, -1};
mn = {-1, -1};
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!f[j][i]) {
if (done)
return 0;
if (h[i].first == -1) h[i].first = j;
if (j - h[i].second > 1 && h[i].second != -1)
return 0;
h[i].second = j;
num++;
}
}
if (h[i].first == -1 && num > 0) done = true;
if (prev.first == -1) {
prev = h[i];
mn = h[i];
continue;
}
if (h[i].first == -1) continue;
if (h[i].first > mn.first && h[i].second > mn.second)
return 0;
if (h[i].first < mn.first && h[i].second < mn.second)
return 0;
mn.first = max(mn.first, h[i].first);
mn.second = min(mn.second, h[i].second);
if (h[i].first > prev.first && h[i].second > prev.second)
return 0;
if (h[i].first < prev.first && h[i].second < prev.second)
return 0;
prev = h[i];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (h[i].first == -1 || h[j].first == -1) continue;
if (h[i].first < h[j].first && h[i].second < h[j].second) return 0;
if (h[i].first > h[j].first && h[i].second > h[j].second) return 0;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (v[i].first == -1 || v[j].first == -1) continue;
if (v[i].first < v[j].first && v[i].second < v[j].second) return 0;
if (v[i].first > v[j].first && v[i].second > v[j].second) return 0;
}
}
return num;
}
int biggest_stadium(int n, vector<vector<int>> f) {
if (n > 3) return tryCase(n, f);
ll numCases = (1 << (n*n));
ll res = 0;
for (int i = 0; i < numCases; i++) {
vector<vector<int>> c(n, vector<int>(n));
ll val = 0;
for (int x = 0; x < n; x++) {
for (int y = 0; y < n; y++) {
ll id = y*n + x;
bool s = i & (1 << id);
if (!s && f[x][y]) goto skip;
c[x][y] = s;
}
}
val = tryCase(n, c);
skip:
res = max(res, val);
}
return res;
}
