This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int biggest_stadium(int n,vector<vector<int> > arr){
int close[2][n][n];
for(int j=0; j<n; j++){
int prv=-1;
for(int i=0; i<n; i++){
if(arr[i][j]) prv=i;
close[0][i][j]=prv;
}
prv=n;
for(int i=n-1; i>=0; i--){
if(arr[i][j]) prv=i;
close[1][i][j]=prv;
}
}
int yay[4][n+5][n+5];
memset(yay,0,sizeof(yay));
for(int i=0; i<n; i++){
vector<pair<int,pair<int,int> > > mono;
//area 0
mono.push_back({n+5,{-1,0}});
int val=0;
for(int j=0; j<n; j++){
while(!mono.empty()&&mono.back().first<close[0][i][j]){
val-=mono.back().second.second;
mono.pop_back();
}
int more=(close[0][i][j]+1)*(j-mono.back().second.first);
val+=more;
mono.push_back({close[0][i][j],{j,more}});
yay[0][i+1][j+1]=val;
}
//area 1
mono.clear();
mono.push_back({n+5,{n,0}});
val=0;
for(int j=n-1; j>=0; j--){
while(!mono.empty()&&mono.back().first<close[0][i][j]){
val-=mono.back().second.second;
mono.pop_back();
}
int more=(close[0][i][j]+1)*(mono.back().second.first-j);
val+=more;
mono.push_back({close[0][i][j],{j,more}});
yay[1][i+1][j+1]=val;
}
//area 2
mono.clear();
mono.push_back({-1,{-1,0}});
val=0;
for(int j=0; j<n; j++){
while(!mono.empty()&&mono.back().first>close[1][i][j]){
val-=mono.back().second.second;
mono.pop_back();
}
int more=(n-close[1][i][j])*(j-mono.back().second.first);
val+=more;
mono.push_back({close[1][i][j],{j,more}});
yay[2][i+1][j+1]=val;
}
//area 3
mono.clear();
mono.push_back({-1,{n,0}});
val=0;
for(int j=n-1; j>=0; j--){
while(!mono.empty()&&mono.back().first>close[1][i][j]){
val-=mono.back().second.second;
mono.pop_back();
}
int more=(n-close[1][i][j])*(mono.back().second.first-j);
val+=more;
mono.push_back({close[1][i][j],{j,more}});
yay[3][i+1][j+1]=val;
}
}
int pref[n+1][n+1];
memset(pref,0,sizeof(pref));
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
pref[i+1][j+1]=pref[i+1][j]+pref[i][j+1]-pref[i][j]+arr[i][j];
}
}
int ans=0;
for(int a=0; a<=n; a++){
for(int b=0; b<=n; b++){
ans=max(ans,n*n-yay[0][a][b]-yay[1][a][b+1]-yay[2][a+1][b]-yay[3][a+1][b+1]);
}
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |