#include "soccer.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
typedef long long ll;
namespace{
const int inf = 1e9;
int dp[31][31][31][31];
}
int biggest_stadium(int N, std::vector<std::vector<int>> F){
int n = N, ans = 0, cnt = 0;
vector<vector<int>> vec(n + 1, vector<int>(n + 1)), pre(n + 1, vector<int>(n + 1));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
vec[i][j] = 1 - F[i - 1][j - 1];
cnt += vec[i][j];
}
}
if(cnt == n * n) return n * n;
if(cnt == n * n - 1){
int px = -1, py = -1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(vec[i][j] == 1) px = i, py = j;
}
}
return n * n - min(px, n - px + 1) * min(py, n - py + 1);
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + vec[i][j];
}
}
auto get = [&](int a, int b, int c, int d){
// (a, b) -> (c, d)
return pre[c][d] - pre[c][b - 1] - pre[a - 1][d] + pre[a - 1][b - 1];
};
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
for(int k = 1; k <= n; k++){
for(int l = 1; l <= n; l++){
dp[i][j][k][l] = -inf;
}
}
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
for(int k = j; k <= n; k++){
if(get(i, j, i, k) == k - j + 1) dp[i][i][j][k] = k - j + 1;
}
}
}
for(int len = 1; len < n; len++){
for(int t = 1; t + len - 1 <= n; t++){
int b = t + len - 1;
for(int l = 1; l <= n; l++){
for(int r = l; r <= n; r++){
if(dp[t][b][l][r] == -inf) continue;
for(int tl = l; tl <= r; tl++){
for(int tr = tl; tr <= r; tr++){
if(t > 1 && get(t - 1, tl, t - 1, tr) == tr - tl + 1) dp[t - 1][b][tl][tr] = max(dp[t - 1][b][tl][tr], dp[t][b][l][r] + tr - tl + 1);
if(b < n && get(b + 1, tl, b + 1, tr) == tr - tl + 1) dp[t][b + 1][tl][tr] = max(dp[t][b + 1][tl][tr], dp[t][b][l][r] + tr - tl + 1);
}
}
}
}
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
for(int k = 1; k <= n; k++){
for(int l = 1; l <= n; l++){
ans = max(ans, dp[i][j][k][l]);
}
}
}
}
return ans;
}
