#include<bits/stdc++.h>
using namespace std;
int biggest_stadium(int N, vector<vector<int>> F)
{
vector<vector<int>> Nextleft(N, vector<int>(N, -1));
vector<int> dp(N, 0), sz(N, 0);
for (int i=0; i<N; i++)
{
for (int j=0; j<N; j++)
{
if (F[i][j]==1)Nextleft[i][j]=j;
else if (j>0)Nextleft[i][j]=Nextleft[i][j-1];
}
}
int maxx=0;
for (int Right=N-1; Right>=0; Right--)
{
vector<int> haut(N), bas(N),cursize(N);
for (int i=0; i<N; i++)
{
haut[i]=i;
bas[i]=i;
}
vector<int> ST;
for (int i=0; i<N; i++)
{
int last=i;
while(!ST.empty() && Nextleft[i][Right]>=Nextleft[ST.back()][Right])
{
last=ST.back();
ST.pop_back();
}
ST.push_back(i);
haut[i]=haut[last];
}
ST.clear();
for (int i=N-1; i>=0; i--)
{
int last=i;
while(!ST.empty() && Nextleft[i][Right]>=Nextleft[ST.back()][Right])
{
last=ST.back();
ST.pop_back();
}
ST.push_back(i);
bas[i]=bas[last];
cursize[i]=bas[i]-haut[i]+1;
}
vector<pair<int,int>> rectangles;
vector<int> l(N,-1), r(N, -1);
for (int i=0; i<N;i ++)
{
l[i]=i-1;
r[i]=i+1;
if (!F[i][Right])rectangles.push_back({Nextleft[i][Right], i});
}
r[N-1]=-1;
sort(rectangles.begin(), rectangles.end());
for (int i=rectangles.size()-1; i>=0; i--)
{
int x=rectangles[i].second;
dp[x]+=(cursize[x]-sz[x])*(Right-Nextleft[x][Right]);
}
for (int i=0; i<N; i++)
{
int x=rectangles[i].second;
if (r[x]!=-1)dp[r[x]]=max(dp[r[x]], dp[x]+((cursize[r[x]]-cursize[x])*(Right-Nextleft[r[x]][Right])));
if (l[x]!=-1)dp[l[x]]=max(dp[l[x]], dp[x]+((cursize[l[x]]-cursize[x])*(Right-Nextleft[l[x]][Right])));
if (r[x]!=-1)l[r[x]]=l[x];
if (l[x]!=-1)r[l[x]]=r[x];
sz[x]=cursize[x];
}
for (int i=0; i<N; i++)
{
if (F[i][Right]==1)
{
maxx=max(maxx, dp[i]);
dp[i]=0;
sz[i]=0;
}
}
}
for (int i=0; i<N; i++)maxx=max(maxx, dp[i]);
return maxx;
}
int main()
{
int N;
cin >> N;
vector<vector<int>> F(N, vector<int>(N));
for (int i=0; i<N; i++)
{
for (int j=0; j<N; j++)
{
cin >> F[i][j];
}
}
cout << biggest_stadium(N, F);
}
Compilation message
/usr/bin/ld: /tmp/ccCe0xEG.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccCCCZMC.o:soccer.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
