#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 500 + 3;
bool f[N][N];
int prefix[N][N];
short p2[N][N][N], prv[N][N][N], nxt[N][N][N];
int n;
int dp[2][N][N];
int get_sum(int i, int l, int r){
if(l == 0)
return prefix[i][r];
return prefix[i][r] - prefix[i][l - 1];
}
bool bad(int l1, int r1, int l2, int r2){
if(l1 <= l2 && r2 <= r1)
return false;
if(l2 <= l1 && r1 <= r2)
return false;
return true;
}
pair<int, int> extend(int i, int j, int l, int r){
assert(prv[l][r][i] == prv[l][r][j]);
assert(nxt[l][r][i] == nxt[l][r][j]);
return {prv[l][r][i], nxt[l][r][j]};
}
int global_ans = 0;
void init_dp(){
for(int l = n - 1; l >= 0; --l){
for(int r = l; r < n; ++r){
for(int i = 0; i < n; ++i){
if(p2[l][r][i])
continue;
auto [p, q] = extend(i, i, l, r);
auto &ans = dp[l & 1][r][p];
ans = 0;
if(l != r){
vector<pair<int, int>> v{{l + 1, r}, {l, r - 1}};
for(auto [l2, r2]: v){
auto [p2, q2] = extend(p, q, l2, r2);
int cand = (p - p2 + q2 - q) * (r2 - l2 + 1);
cand += dp[l2 & 1][r2][p2];
ans = max(ans, cand);
}
}
global_ans = max(global_ans, ans + (q - p + 1) * (r - l + 1));
}
}
}
}
int biggest_stadium(int _N, std::vector<std::vector<int>> F){
n = _N;
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
f[i][j] = F[i][j];
for(int i = 0; i < n; ++i){
prefix[i][0] = f[i][0];
for(int j = 1; j < n; ++j)
prefix[i][j] = prefix[i][j - 1] + f[i][j];
}
for(int l = 0; l < n; ++l){
for(int r = l; r < n; ++r){
for(int i = 0; i < n; ++i){
p2[l][r][i] = (bool)get_sum(i, l, r);
}
}
}
for(int l = 0; l < n; ++l){
for(int r = l; r < n; ++r){
int x = 0;
for(int i = 0; i < n; ++i){
if(p2[l][r][i]){
x = i + 1;
}
else{
prv[l][r][i] = x;
}
}
x = n - 1;
for(int i = n - 1; i >= 0; --i){
if(p2[l][r][i]){
x = i - 1;
}
else{
nxt[l][r][i] = x;
}
}
}
}
init_dp();
return global_ans;
}
/*
3
1 1 1
1 1 1
1 1 1
*/
