#include "soccer.h"
#include <iostream>
using namespace std;
#define pb push_back
#define mp make_pair
#define plist(x) if(1==0){for(auto e:x)cout<<e<<",";cout<<"\n";}
#define dout if(1==0)cout
// (y,x)
int biggest_stadium(int n, vector<vector<int>> f){
vector<int> treesH(1,-1), treesV(1,-1); // H means the rows themselves are horizontal (!)
vector<int> tH(n,0), tV(n,0);
pair<int, int> tree = mp(-1,-1);
for(int y=0; y<n; y++){
for(int x=0; x<n; x++){
if(f[y][x]){
tree = mp(y,x);
treesH.pb(x);
treesV.pb(y);
tH[y]=1;
tV[x]=1;
}
}
}
cerr<<"treesH: ";plist(treesH);
cerr<<"treesV: ";plist(treesV);
vector<int> gridV, gridH;
for(int x=0; x<=n; x++){
if(x==0 || (x>0 && tV[x-1]) || (x<n && tV[x]) || x==n){
gridV.pb(x);
}
}
for(int y=0; y<=n; y++){
if(y==0 || (y>0 && tH[y-1]) || (y<n && tH[y]) || y==n){
gridH.pb(y);
}
}
cerr<<"gridH: ";plist(gridH);
cerr<<"gridV: ";plist(gridV);
int N=gridH.size()-1;
int M=gridV.size()-1;
vector<vector<int>> ar(N);
for(int y=0; y<N; y++){
for(int x=0; x<M; x++){
ar[y].pb((gridV[x+1]-gridV[x])*(gridH[y+1]-gridH[y]));
if(ar[y][x]==1 && f[gridH[y]][gridV[x]]/*..*/){
ar[y][x]=0;
}
}
}
if(1==1){
cerr<<"here it comes:\n";
for(int y=0; y<N; y++){
for(int x=0; x<M; x++){
cerr<<ar[y][x]<<" ";
}
cerr<<"\n";
}
}
swap(n,N);
int m=M;
int answer=0, cursum;
int low,high,curlow,curhigh;
dout<<"(n,m) >> ("<<n<<","<<m<<")\n";
for(int y=0; y<n; y++){
for(int x=0; x<m; x++){
// what if this was the central square?
if(ar[y][x]==0)continue; // can't play in a tree :(
cursum=0;
low=-1; high=n;
// find highs and lows (and do search on this column)
for(int ny=y; ny>low; ny--){
if(ar[ny][x]==0){
low=ny;
} else{
cursum += ar[ny][x];
}
}
for(int ny=y+1; ny<high; ny++){
if(ar[ny][x]==0){
high=ny;
} else{
cursum += ar[ny][x];
}
}
// go to the RIGHT
curhigh = high;
curlow = low;
for(int nx=x+1; nx<m; nx++){
if(ar[y][nx]==0)break;
for(int ny=y; ny>curlow; ny--){
if(ar[ny][nx]==0){
curlow=ny;
} else{
cursum += ar[ny][nx];
}
}
for(int ny=y+1; ny<curhigh; ny++){
if(ar[ny][nx]==0){
curhigh=ny;
} else{
cursum += ar[ny][nx];
}
}
}
// go to the LEFT
curhigh = high;
curlow = low;
for(int nx=x-1; nx>-1; nx--){
if(ar[y][nx]==0)break;
for(int ny=y; ny>curlow; ny--){
if(ar[ny][nx]==0){
curlow=ny;
} else{
cursum += ar[ny][nx];
}
}
for(int ny=y+1; ny<curhigh; ny++){
if(ar[ny][nx]==0){
curhigh=ny;
} else{
cursum += ar[ny][nx];
}
}
}
answer = max(answer, cursum);
}
}
return answer;
}
