Submission #844920

#TimeUsernameProblemLanguageResultExecution timeMemory
844920LibSoccer Stadium (IOI23_soccer)C++17
8 / 100
4543 ms7260 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...