#include <bits/stdc++.h>
#include "soccer.h"
using namespace std;

const int N=2005;

int a[N][N],l[N][N],r[N][N],dp[N][N],pre[N][N],nex[N][N];

int biggest_stadium(int n,vector<vector<int> > F)
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            a[i][j]=F[i-1][j-1];

    if(n<=500)
    {
        for(int i=1;i<=n;i++)
        {
            int now=0;
            for(int j=1;j<=n;j++)
            {
                if(a[i][j])
                    now=j;
                pre[i][j]=now;
            }

            now=n+1;
            for(int j=n;j>=1;j--)
            {
                if(a[i][j])
                    now=j;
                nex[i][j]=now;
            }
        }

        int ans=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
                l[j][j]=pre[j][i]+1, r[j][j]=nex[j][i]-1, dp[j][j]=max(0,r[j][j]-l[j][j]+1);

            for(int len=2;len<=n;len++)
                for(int i=1;i+len-1<=n;i++)
                {
                    int j=i+len-1;
                    l[i][j]=max(l[i][j-1],l[j][j]);
                    r[i][j]=min(r[i][j-1],r[j][j]);
                    dp[i][j]=max(dp[i][j-1],dp[i+1][j])+max(0,r[i][j]-l[i][j]+1);
                }

            ans=max(ans,dp[1][n]);
        }
        return ans;
    }

    if(n<=2000)
    {
        for(int i=1;i<=n;i++)
        {
            int now=0;
            for(int j=1;j<=n;j++)
            {
                if(a[i][j])
                    now=j;
                pre[i][j]=now;
            }

            now=n+1;
            for(int j=n;j>=1;j--)
            {
                if(a[i][j])
                    now=j;
                nex[i][j]=now;
            }
        }

        int ans=0;
        int i=n;
        for(int j=1;j<=n;j++)
            l[j][j]=pre[j][i]+1, r[j][j]=nex[j][i]-1, dp[j][j]=max(0,r[j][j]-l[j][j]+1);

        for(int len=2;len<=n;len++)
            for(int i=1;i+len-1<=n;i++)
            {
                int j=i+len-1;
                l[i][j]=max(l[i][j-1],l[j][j]);
                r[i][j]=min(r[i][j-1],r[j][j]);
                dp[i][j]=max(dp[i][j-1],dp[i+1][j])+max(0,r[i][j]-l[i][j]+1);
            }
        ans=max(ans,dp[1][n]);

        i=1;
        for(int j=1;j<=n;j++)
            l[j][j]=pre[j][i]+1, r[j][j]=nex[j][i]-1, dp[j][j]=max(0,r[j][j]-l[j][j]+1);

        for(int len=2;len<=n;len++)
            for(int i=1;i+len-1<=n;i++)
            {
                int j=i+len-1;
                l[i][j]=max(l[i][j-1],l[j][j]);
                r[i][j]=min(r[i][j-1],r[j][j]);
                dp[i][j]=max(dp[i][j-1],dp[i+1][j])+max(0,r[i][j]-l[i][j]+1);
            }
        ans=max(ans,dp[1][n]);

        int pos=0, Maxcnt=0;
        for(int i=1;i<=n;i++)
        {
            int cnt=0;
            for(int j=1;j<=n;j++)
                if(a[j][i]==0)
                    cnt++;

            if(cnt>Maxcnt)
                Maxcnt=cnt, pos=i;
        }

        i=pos;
        for(int j=1;j<=n;j++)
            l[j][j]=pre[j][i]+1, r[j][j]=nex[j][i]-1, dp[j][j]=max(0,r[j][j]-l[j][j]+1);

        for(int len=2;len<=n;len++)
            for(int i=1;i+len-1<=n;i++)
            {
                int j=i+len-1;
                l[i][j]=max(l[i][j-1],l[j][j]);
                r[i][j]=min(r[i][j-1],r[j][j]);
                dp[i][j]=max(dp[i][j-1],dp[i+1][j])+max(0,r[i][j]-l[i][j]+1);
            }
        ans=max(ans,dp[1][n]);
        return ans;
    }
}