#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 33, M = 2002;
int n;
int p[M][M];
int l2[M], r2[M];
int dp[N][N][N][N];
void maxh(int& x, int y)
{
x = max(x, y);
}
int biggest_stadium(int N, std::vector<std::vector<int> > F)
{
n = N;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
p[i][j] = p[i][j - 1] + F[i - 1][j - 1];
}
}
int maxu = 0;
int maxi = 0;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
if (F[i - 1][j - 1] == 0)
{
l2[i] = j;
break;
}
}
for (int j = n; j >= 1; --j)
{
if (F[i - 1][j - 1] == 0)
{
r2[i] = j;
break;
}
}
if (p[i][r2[i]] - p[i][l2[i] - 1] > 0)
return 0;
if (r2[i] - l2[i] + 1 > maxu)
{
maxu = r2[i] - l2[i] + 1;
maxi = i;
}
}
int l0 = maxi;
int r0 = maxi;
int l = l2[maxi];
int r = r2[maxi];
while (1)
{
int sl0 = l0;
int sr0 = r0;
if (l2[l0 - 1])
{
if (l <= l2[l0 - 1] && r2[l0 - 1] <= r)
{
--l0;
l = l2[l0];
r = r2[l0];
}
}
if (r2[r0 + 1])
{
if (l <= l2[r0 + 1] && r2[r0 + 1] <= r)
{
++r0;
l = l2[r0];
r = r2[r0];
}
}
if (m_p(l0, r0) == m_p(sl0, sr0))
break;
}
for (int i = 1; i < l0; ++i)
{
if (l2[i])
return 0;
}
for (int i = r0 + 1; i <= n; ++i)
{
if (r2[i])
return 0;
}
int ans = 0;
for (int i = 1; i <= n; ++i)
ans += p[i][n];
return ans;
/*for (int i = 1; i <= n; ++i)
{
for (int l = 1; l <= n; ++l)
{
for (int r = l; r <= n; ++r)
{
if (p[i][r] - p[i][l - 1] == 0)
dp[i][i][l][r] = r - l + 1;
}
}
}
int ans = 0;
for (int d0 = 1; d0 <= n; ++d0)
{
for (int l0 = 1; l0 + d0 - 1 <= n; ++l0)
{
int r0 = l0 + d0 - 1;
for (int d = n; d >= 1; --d)
{
for (int l = 1; l + d - 1 <= n; ++l)
{
int r = l + d - 1;
maxh(dp[l0][r0][l][r - 1], dp[l0][r0][l][r]);
maxh(dp[l0][r0][l + 1][r], dp[l0][r0][l][r]);
if (p[l0 - 1][r] - p[l0 - 1][l - 1] == 0)
maxh(dp[l0 - 1][r0][l][r], dp[l0][r0][l][r] + r - l + 1);
if (p[r0 + 1][r] - p[r0 + 1][l - 1] == 0)
maxh(dp[l0][r0 + 1][l][r], dp[l0][r0][l][r] + r - l + 1);
maxh(ans, dp[l0][r0][l][r]);
}
}
}
}
return ans;*/
}
/*
5
1 1 1 1 1
1 1 1 1 1
1 0 0 1 1
1 0 0 0 1
1 1 0 0 1
5
0 0 0 0 0
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
*/
