#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
int check_all( vector<vector<int>> &mat ){
int n = mat.size();
vector<int> l(n, n), r(n, -1);
int tot = 0;
for( int i = 0; i < n; i++ )
for( int j = 0; j < n; j++ ) if( mat[i][j] == 0 ){
tot++;
l[i] = min( l[i], j );
r[i] = max( r[i], j );
}
return tot;
auto contains = [&]( int a, int b ){
return l[a] <= l[b] && r[b] <= r[a];
};
int cont = 0;
for( int i = 0; i < n; i++ ) if( l[i] != n ){
cont += (r[i] - l[i] + 1);
for( int j = i + 1; j < n; j++ ) if( l[j] != n && !contains( i, j ) && !contains( j, i ) ) return 0;
}
if( tot < cont ) return 0;
fill( l.begin(), l.end(), n );
fill( r.begin(), r.end(), -1 );
for( int i = 0; i < n; i++ )
for( int j = 0; j < n; j++ ) if( mat[j][i] == 0 ){
l[i] = min( l[i], j );
r[i] = max( r[i], j );
}
cont = 0;
for( int i = 0; i < n; i++ ) if( l[i] != n ){
cont += (r[i] - l[i] + 1);
for( int j = i + 1; j < n; j++ ) if( l[j] != n && !contains( i, j ) && !contains( j, i ) ) return 0;
}
if( tot < cont ) return 0;
return tot;
}
const int maxn = 50;
const int inf = 1e5;
int dp[maxn][maxn][maxn][maxn];
int sum[maxn][maxn];
int n;
int query( int l, int r, int u, int d ){
return sum[d][r] - sum[d][l - 1] - sum[u - 1][r] + sum[u - 1][l - 1];
}
int solve( int l, int r, int u, int d ){
if( l < 0 || r >= n || u < 0 || d >= n ) return -inf;
if( u > d ) return 0;
if( query( l + 1, r + 1, u + 1, d + 1 ) ) return -inf;
if( dp[l][r][u][d] != -1 ) return dp[l][r][u][d];
dp[l][r][u][d] = max({ solve( l - 1, r, u, d ) + (d - u + 1),
solve( l, r + 1, u, d ) + (d - u + 1),
solve( l, r, u + 1, d ),
solve( l, r, u, d - 1 ) });
return dp[l][r][u][d];
}
int solve1( vector<vector<int>> &mat ){
int n = mat.size();
int a, b;
for( int i = 0; i < n; i++ ) for(int j = 0; j < n; j++ ) if( mat[i][j] == 1 ) a = i, b = j;
return n*n - min( a + 1, n - a )*min( b + 1, n - b );
}
int biggest_stadium(int N, vector<vector<int>> mat ){
int total = check_all(mat);
if( total + 1 == N*N ) return solve1(mat);
n = N;
for( int i = 0; i < n; i++ ) for( int j = 0; j < n; j++ ) for( int k = 0; k < n; k++ ) for( int l = 0; l < n; l++ ) dp[i][j][k][l] = -1;
for( int i = 1; i <= n; i++ ) for( int j = 1; j <= n; j++ )
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i - 1][j - 1];
int resp = 0;
vector<int> h(n);
for( int i = 0; i < n; i++ ){
for( int j = 0; j < n; j++ ){
if( mat[i][j] == 0 ) h[j]++;
else h[j] = 0;
resp = max( resp, solve( j, j, i - h[j] + 1, i ) + h[j] );
}
}
return resp;
}
