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

const int MX=35;

int sum[MX][MX];
int dp[MX][MX][MX][MX];

bool check(int c, int a, int b) {
        int res=sum[b][c];
        if(a>0) res-=sum[a-1][c];
        return res==0;
}

int biggest_stadium(int N, std::vector<std::vector<int>> F) {
        for(int i=0;i<N;i++) {
                for(int j=0;j<N;j++) {
                        for(int l=0;l<N;l++) {
                                for(int r=0;r<N;r++) {
                                        dp[i][j][l][r]=-1;
                                }
                        }
                }
        }
        

        for(int i=0;i<N;i++) {
                for(int j=0;j<N;j++) {
                        sum[i][j]+=F[i][j];
                        if(i>0) sum[i][j]+=sum[i-1][j];
                }
        }

        for(int l=0;l<N;l++) {
                for(int x=0;x<N;x++) {
                        for(int y=x;y<N;y++) {
                                if(!check(l,x,y)) continue;
                                dp[l][l][x][y]=y-x+1;
                        }
                }
        }

        for(int l=N-1;l>=0;l--) {
                for(int r=l;r<N;r++) { // horizontal range
                        for(int x=0;x<N;x++) {
                                for(int y=x;y<N;y++) { // vertical range
                                        if(dp[l][r][x][y]==-1) continue;
                                        for(int cx=x;cx<=y;cx++) {
                                                for(int cy=cx;cy<=y;cy++) {
                                                        if(l-1>=0 && check(l-1,cx,cy)) {
                                                                dp[l-1][r][cx][cy]=max(dp[l-1][r][cx][cy],dp[l][r][x][y]+(cy-cx+1));
                                                        }
                                                        if(r+1<N && check(r+1,cx,cy)) {
                                                                dp[l][r+1][cx][cy]=max(dp[l][r+1][cx][cy],dp[l][r][x][y]+(cy-cx+1));
                                                        }
                                                }
                                        }

                                }
                        }


                }       
        }

        int ans=0;
        for(int i=0;i<N;i++) {
                for(int j=i;j<N;j++) {
                        for(int l=0;l<N;l++) {
                                for(int r=l;r<N;r++) {
                                        ans=max(ans,dp[i][j][l][r]);
                                }
                        }
                }
        }

        return ans;
}