#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
// #define int long long // remove when necessary
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
#define ll long long
int brute(int n, vector<vector<int>> F) {
int ans = 0;
bool take[n][n];
for (int conf = 0; conf < (1 << (n * n)); conf++) {
bool valid = true;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
take[i][j] = bool(conf & (1 << (i * n + j)));
if (take[i][j] && F[i][j]) {
valid = false;
}
}
}
if (!valid) continue;
for (int x = 0; x < n * n; x++) {
for (int y = 0; y < n * n; y++) {
int x1 = x / n, x2 = x % n;
int y1 = y / n, y2 = y % n;
if (!take[x1][x2] || !take[y1][y2]) continue;
pii cur; bool can;
cur = {x1, x2}; can = 1;
while (cur.ff != y1) {
cur.ff += (cur.ff < y1 ? 1 : -1);
can &= take[cur.ff][cur.ss];
}
while (cur.ss != y2) {
cur.ss += (cur.ss < y2 ? 1 : -1);
can &= take[cur.ff][cur.ss];
}
if (can) continue;
cur = {x1, x2}; can = 1;
while (cur.ss != y2) {
cur.ss += (cur.ss < y2 ? 1 : -1);
can &= take[cur.ff][cur.ss];
}
while (cur.ff != y1) {
cur.ff += (cur.ff < y1 ? 1 : -1);
can &= take[cur.ff][cur.ss];
}
if (can) continue;
valid = false;
break;
}
if (!valid) break;
}
if (valid) ans = max(ans, __builtin_popcount(conf));
}
return ans;
}
bool check(int n, vector<vector<int>> F) {
bool take[n][n];
bool valid = true;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
take[i][j] = (F[i][j] ? 0 : 1);
}
}
for (int x = 0; x < n * n; x++) {
for (int y = 0; y < n * n; y++) {
int x1 = x / n, x2 = x % n;
int y1 = y / n, y2 = y % n;
if (!take[x1][x2] || !take[y1][y2]) continue;
pii cur; bool can;
cur = {x1, x2}; can = 1;
while (cur.ff != y1) {
cur.ff += (cur.ff < y1 ? 1 : -1);
can &= take[cur.ff][cur.ss];
}
while (cur.ss != y2) {
cur.ss += (cur.ss < y2 ? 1 : -1);
can &= take[cur.ff][cur.ss];
}
if (can) continue;
cur = {x1, x2}; can = 1;
while (cur.ss != y2) {
cur.ss += (cur.ss < y2 ? 1 : -1);
can &= take[cur.ff][cur.ss];
}
while (cur.ff != y1) {
cur.ff += (cur.ff < y1 ? 1 : -1);
can &= take[cur.ff][cur.ss];
}
if (can) continue;
return false;
}
}
return true;
}
const int MIN = -1e9;
int biggest_stadium(int n, vector<vector<int>> F)
{
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cnt += (F[i][j] ? 0 : 1);
}
}
return (check(n, F) ? cnt : 0);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (F[i][j]) {
int ans = 0;
ans = max(ans, i * n + j * n - i * j);
ans = max(ans, i * n + (n - j - 1) * n - i * (n - j - 1));
ans = max(ans, (n - i - 1) * n + j * n - (n - i - 1) * j);
ans = max(ans, (n - i - 1) * n + (n - j - 1) * n - (n - i - 1) * (n - j - 1));
return ans;
}
}
}
return n * n;
if (n <= 3) return brute(n, F);
if (n > 500) return 0;
if (n == 1) return (F[0][0] ? 0 : 1);
if (n == 2) {
int ans = 4;
ans -= F[0][0];
ans -= F[0][1];
ans -= F[1][0];
ans -= F[1][1];
if (F[0][0] && !F[0][1] && !F[1][0] && F[1][1]) ans--;
if (!F[0][0] && F[0][1] && F[1][0] && !F[1][1]) ans--;
return ans;
}
bool a[n + 1][n + 1];
int ps[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
ps[i][0] = 0;
for (int j = 1; j <= n; j++) {
a[i][j] = F[i - 1][j - 1];
ps[i][j] = ps[i][j - 1] + a[i][j];
}
}
int dp[2][n + 1][n + 1][n + 1]; // dp[vert pos][l range][r range]
int dpm[2][n + 1][n + 1][n + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
for (int k = 0; k <= n; k++) {
dp[0][i][j][k] = dp[1][i][j][k] = 0;
dpm[0][i][j][k] = dpm[1][i][j][k] = 0;
}
}
}
for (int i = 1; i <= n; i++) {
for (int l = 1; l <= n; l++) {
for (int r = l; r <= n; r++) {
if (ps[i][r] - ps[i][l - 1]) {
dp[0][i][l][r] = 0;
dp[1][i][l][r] = 0;
} else {
dp[0][i][l][r] = dpm[0][i - 1][l][r] + (r - l + 1);
dp[1][i][l][r] = dpm[1][i - 1][l][r] + (r - l + 1);
}
}
}
for (int j = 1; j <= n; j++) {
dpm[0][i][j][j] = dp[0][i][j][j];
}
for (int diff = 1; diff < n; diff++) {
for (int l = 1, r = 1 + diff; r <= n; l++, r++) {
dpm[0][i][l][r] = max(max(dpm[0][i][l + 1][r], dpm[0][i][l][r - 1]), dp[0][i][l][r]);
}
}
dpm[1][i][1][n] = max(dp[0][i][1][n], dp[1][i][1][n]);
for (int diff = n - 2; diff >= 0; diff--) {
for (int l = 1, r = 1 + diff; r <= n; l++, r++) {
dpm[1][i][l][r] = max(dp[0][i][l][r], dp[1][i][l][r]);
if (l > 1) {
dpm[1][i][l][r] = max(dpm[1][i][l][r], dpm[1][i][l - 1][r]);
}
if (r < n) {
dpm[1][i][l][r] = max(dpm[1][i][l][r], dpm[1][i][l][r + 1]);
}
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int k = j; k <= n; k++) {
// cerr << i << ' ' << j << ' ' << k << ": ";
// cerr << dp[0][i][j][k] << ", " << dp[1][i][j][k] << " | ";
// cerr << dpm[0][i][j][k] << ", " << dpm[1][i][j][k] << endl;
ans = max(ans, dp[0][i][j][k]);
ans = max(ans, dp[1][i][j][k]);
}
}
}
return ans;
}
