#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 = 502, M = 2002;
int n;
int p[M][M];
int dp1[N][N][N], dp2[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];
}
}
for (int i = 1; i <= n; ++i)
{
for (int d = 1; d <= n; ++d)
{
for (int l = 1; l + d - 1 <= n; ++l)
{
int r = l + d - 1;
maxh(dp1[i - 1][l - 1][r], dp1[i - 1][l][r]);
maxh(dp1[i - 1][l][r + 1], dp1[i - 1][l][r]);
}
}
for (int l = 1; l <= n; ++l)
{
for (int r = l; r <= n; ++r)
{
if (p[i][r] - p[i][l - 1] == 0)
maxh(dp1[i][l][r], dp1[i - 1][l][r] + r - l + 1);
}
}
}
for (int i = n; i >= 1; --i)
{
for (int d = 1; d <= n; ++d)
{
for (int l = 1; l + d - 1 <= n; ++l)
{
int r = l + d - 1;
maxh(dp2[i + 1][l - 1][r], dp2[i + 1][l][r]);
maxh(dp2[i + 1][l][r + 1], dp2[i + 1][l][r]);
}
}
for (int l = 1; l <= n; ++l)
{
for (int r = l; r <= n; ++r)
{
if (p[i][r] - p[i][l - 1] == 0)
maxh(dp2[i][l][r], dp2[i + 1][l][r] + r - l + 1);
}
}
}
int ans = 0;
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)
maxh(ans, dp1[i - 1][l][r] + dp2[i + 1][l][r] + r - l + 1);
}
}
}
return ans;
}
/*
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
*/
