#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
int size(pair<int,int> a) { return a.second - a.first + 1; }
bool checkIntervals(pair<int,int> a, pair<int,int> b) { return (b.first <= a.first && a.second <= b.second); }
bool isGood(int N, vector<vector<int>>& F)
{
vector<pair<int,int>> intervals;
for(int i = 0 ; i < N ; i++)
{
int numCells = 0;
int minCell = N, maxCell = -1;
for(int j = 0 ; j < N ; j++)
{
if( F[i][j] == 0 )
{
numCells++;
minCell = min( minCell , j );
maxCell = max( maxCell , j );
}
}
if( numCells == 0 )
continue;
if( numCells != maxCell - minCell + 1 )
return false;
intervals.push_back( { minCell , maxCell } );
}
int p = 0;
while( p + 1 < (int)intervals.size() && size(intervals[p]) <= size(intervals[p + 1]) )
{
if( !checkIntervals( intervals[p] , intervals[p + 1] ) )
return false;
p++;
}
while( p + 1 < (int)intervals.size() && size(intervals[p]) >= size(intervals[p + 1]) )
{
if( !checkIntervals( intervals[p + 1] , intervals[p] ) )
return false;
p++;
}
if( p != (int)intervals.size() - 1 )
return false;
sort( intervals.begin() , intervals.end() , [&](pair<int,int> a, pair<int,int> b){
return size(a) < size(b);
});
for(int i = 0 ; i + 1 < (int)intervals.size() ; i++)
if( !checkIntervals( intervals[i] , intervals[i + 1] ) ) return false;
return true;
}
int biggest_stadium(int N, vector<vector<int>> F)
{
if( !isGood(N, F) )
return -1;
int sum = 0;
for(int i = 0 ; i < N ; i++)
for(int j = 0 ; j < N ; j++)
sum += 1 - F[i][j];
return sum;
}
