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[4][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;
}
}
for(int i=0; i<n; i++){
int prv=-1;
for(int j=0; j<n; j++){
if(arr[i][j]) prv=j;
close[2][i][j]=prv;
}
prv=n;
for(int j=n-1; j>=0; j--){
if(arr[i][j]) prv=j;
close[3][i][j]=prv;
}
}
int pref[4][n+5][n+5];
memset(pref,0,sizeof(pref));
for(int i=0; i<n; i++) for(int j=0; j<n; j++) arr[i][j]^=1;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
pref[0][i+1][j+1]=pref[0][i+1][j]+pref[0][i][j+1]-pref[0][i][j]+arr[i][j];
}
for(int j=n-1; j>=0; j--){
pref[1][i+1][j+1]=pref[1][i+1][j+2]+pref[1][i][j+1]-pref[1][i][j+2]+arr[i][j];
}
}
for(int i=n-1; i>=0; i--){
for(int j=0; j<n; j++){
pref[2][i+1][j+1]=pref[2][i+1][j]+pref[2][i+2][j+1]-pref[2][i+2][j]+arr[i][j];
}
for(int j=n-1; j>=0; j--){
pref[3][i+1][j+1]=pref[3][i+1][j+2]+pref[3][i+2][j+1]-pref[3][i+2][j+2]+arr[i][j];
}
}
for(int a=1; a<=n; a++){
for(int b=1; b<=n; b++){
if(arr[a-1][b-1]==0) continue;
int u=close[0][a-1][b-1],d=close[1][a-1][b-1],l=close[2][a-1][b-1],r=close[3][a-1][b-1];
//cout << a << ' ' << b << '\n';
//cout << u << ' ' << d << ' ' << l << ' ' << r << '\n';
if(pref[0][u+1][l+1]) return 0;
if(pref[1][u+1][r+1]) return 0;
if(pref[2][d+1][l+1]) return 0;
if(pref[3][d+1][r+1]) return 0;
}
}
return pref[0][n][n];
}
# | 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... |