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 "soccer.h"
#include <bits/stdc++.h>
using namespace std;
int val[503][503];
int cntop[503];
int cnbot[503];
int mtop[503];
int mbot[503];
int dp[503][503][4];
int biggest_stadium(int N, std::vector<std::vector<int>> C)
{
int n=N;
for(int i=0;i<=n+1;i++){
for(int k=0;k<=n+1;k++){
val[i][k]=1;
}
}
for (int i = 0; i < N ; ++i)
{
for (int j = 0; j < N ; ++j)
{
val[i+1][j+1]=C[i][j];
}
}
int p1,p2;
int ans=0;
int carea;
int add;
for(int i=1;i<=n;i++){
for(int k=1;k<=n;k++){
for(int l=0;i-l>=0;l++){
if(val[i-l][k]){
cntop[k]=l;
break;
}
}
for(int l=0;i+l<=n+1;l++){
if(val[i+l][k]){
cnbot[k]=l;
break;
}
}
}
for(int k=1;k<=n;k++){
if(cntop[k]!=0){
mtop[k]=cntop[k];
mbot[k]=cnbot[k];
p1=k-1;
p2=k+1;
for(int c=0;c<4;c++){
for(int a=1;a<=n;a++){
for(int b=1;b<=n;b++){
dp[a][b][c]=0;
}
}
dp[k][k][c]=cntop[k]+cnbot[k]-1;
while(p1>0&&cntop[p1]){
mtop[p1]=min(cntop[p1],mtop[p1+1]);
mbot[p1]=min(cnbot[p1],mbot[p1+1]);
dp[p1][k][c]=dp[p1+1][k][c]+mtop[p1]+mbot[p1]-1;
p1--;
}
while(p2<=n&&cntop[p2]){
mtop[p2]=min(cntop[p2],mtop[p2-1]);
mbot[p2]=min(cnbot[p2],mbot[p2-1]);
dp[k][p2][c]=dp[k][p2-1][c]+mtop[p2]+mbot[p2]-1;
p2++;
}
//cout<<p1<<" "<<p2<<"\n";
for(int a=3;a<=p2-p1-1;a++){
for(int b=1;b<=a-2;b++){//r:k+b, l=k-(a-b-1)
if(c==0){
add=mtop[k+b]-min(mtop[k+b],mtop[k-(a-b-1)]);
}
if(c==1){
add=mtop[(k-(a-b-1))]-min(mtop[k+b],mtop[k-(a-b-1)]);
}
if(c==2){
add=mbot[(k-(a-b-1))]-min(mbot[k+b],mbot[k-(a-b-1)]);
}
if(c==3){
add=mbot[k+b]-min(mbot[k+b],mbot[k-(a-b-1)]);
}
if(k-(a-b-1)>0&&k+b<=n){
if(mtop[k+b]<=mtop[k-(a-b-1)]&&mbot[k+b]<=mbot[k-(a-b-1)]||mtop[k+b]>=mtop[k-(a-b-1)]&&mbot[k+b]>=mbot[k-(a-b-1)]){
dp[k-(a-b-1)][k+b][c]=dp[k-(a-b-1)+1][k+b-1][c]+mtop[k+b]+mbot[k+b]+mtop[k-(a-b-1)]+mbot[k-(a-b-1)]-2;
}else{
dp[k-(a-b-1)][k+b][c]=dp[k-(a-b-1)+1][k+b-1][c]+min(mtop[k+b],mtop[k-(a-b-1)])*2+min(mbot[k+b],mbot[k-(a-b-1)])*2-2+add;
}
ans=max(ans,dp[k-(a-b-1)][k+b][c]);
//cout<<i<<" "<<k<<" "<<k-(a-b-1)<<" "<<k+b<<" "<<dp[k-(a-b-1)][k+b]<<"\n";
}
}
}
for(int a=p1+1;a<=k;a++){
for(int b=k;b<=p2-1;b++){
ans=max(ans,dp[a][b][c]);
}
}
}
}
}
}
return ans;
}
Compilation message (stderr)
soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:86:36: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
86 | if(mtop[k+b]<=mtop[k-(a-b-1)]&&mbot[k+b]<=mbot[k-(a-b-1)]||mtop[k+b]>=mtop[k-(a-b-1)]&&mbot[k+b]>=mbot[k-(a-b-1)]){
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:28:6: warning: unused variable 'carea' [-Wunused-variable]
28 | int carea;
| ^~~~~
soccer.cpp:89:123: warning: 'add' may be used uninitialized in this function [-Wmaybe-uninitialized]
89 | dp[k-(a-b-1)][k+b][c]=dp[k-(a-b-1)+1][k+b-1][c]+min(mtop[k+b],mtop[k-(a-b-1)])*2+min(mbot[k+b],mbot[k-(a-b-1)])*2-2+add;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
# | 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... |