Submission #40147

#TimeUsernameProblemLanguageResultExecution timeMemory
40147tiger13084Retro (COCI17_retro)C++14
8 / 100
222 ms226504 KiB
#include<stdio.h> #include<algorithm> #define inf 2e9 using namespace std; char In[305][305]; int Dp[305][305][155]; int n,m; struct xx{ int x,y,k; }Bef[305][305][155]; int check(int x,int y){ if(y==0||y==m+1||In[x][y]=='*') return 0; return 1; } xx makeBef(int x,int y,int k){ xx temp; temp.x=x; temp.y=y; temp.k=k; return temp; } main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) scanf(" %c",&In[n-i+1][j]); } for(int j=1;j<=m;j++){ for(int k=0;k<=n/2;k++) Dp[1][j][k]=-inf; if(In[1][j]=='M') Dp[1][j][0]=0; } int ans=0,x,y; for(int i=2;i<=n;i++){ for(int j=1;j<=m;j++){ if(In[i][j]=='('){ for(int k=1;k<=n/2;k++){ int temp=-inf; if(check(i-1,j-1)&&temp<Dp[i-1][j-1][k-1]){ temp=Dp[i-1][j-1][k-1]; Bef[i][j][k]=makeBef(i-1,j-1,k-1); } if(check(i-1,j)&&temp<Dp[i-1][j][k-1]){ temp=Dp[i-1][j][k-1]; Bef[i][j][k]=makeBef(i-1,j,k-1); } if(check(i-1,j+1)&&temp<Dp[i-1][j+1][k-1]){ temp=Dp[i-1][j+1][k-1]; Bef[i][j][k]=makeBef(i-1,j+1,k-1); } Dp[i][j][k]=temp; } } else if(In[i][j]==')'){ for(int k=0;k<=n/2-1;k++){ int temp=-inf; if(check(i-1,j-1)&&temp<Dp[i-1][j-1][k+1]){ temp=Dp[i-1][j-1][k+1]; Bef[i][j][k]=makeBef(i-1,j-1,k+1); } if(check(i-1,j)&&temp<Dp[i-1][j][k+1]){ temp=Dp[i-1][j][k+1]; Bef[i][j][k]=makeBef(i-1,j,k+1); } if(check(i-1,j+1)&&temp<Dp[i-1][j+1][k+1]){ temp=Dp[i-1][j+1][k+1]; Bef[i][j][k]=makeBef(i-1,j+1,k+1); } Dp[i][j][k]=temp+1; } } else { for(int k=0;k<=n/2;k++){ int temp=-inf; if(check(i-1,j-1)&&temp<Dp[i-1][j-1][k]){ temp=Dp[i-1][j-1][k]; Bef[i][j][k]=makeBef(i-1,j-1,k); } if(check(i-1,j)&&temp<Dp[i-1][j][k]){ temp=Dp[i-1][j][k]; Bef[i][j][k]=makeBef(i-1,j,k); } if(check(i-1,j+1)&&temp<Dp[i-1][j+1][k]){ temp=Dp[i-1][j+1][k]; Bef[i][j][k]=makeBef(i-1,j+1,k); } Dp[i][j][k]=temp; } } if(In[i][j]=='*'){ if(ans<Dp[i][j][0]){ ans=Dp[i][j][0]; x=i,y=j; } } } } for(int j=1;j<=m;j++){ if(ans<Dp[n][j][0]){ ans=Dp[n][j][0]; x=n,y=j; } } printf("%d\n",ans*2); xx temp=makeBef(x,y,0); char S[205]; int a=0; while(temp.x>1){ if(In[temp.x][temp.y]=='('||In[temp.x][temp.y]==')') S[++a]=In[temp.x][temp.y]; temp=Bef[temp.x][temp.y][temp.k]; } for(int i=a;i>=1;i--) printf("%c",S[i]); }

Compilation message (stderr)

retro.cpp:28:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
retro.cpp: In function 'int main()':
retro.cpp:29:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
                        ^
retro.cpp:32:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf(" %c",&In[n-i+1][j]);
                                       ^
retro.cpp:118:41: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
         temp=Bef[temp.x][temp.y][temp.k];
                                         ^
retro.cpp:118:41: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
#Verdict Execution timeMemoryGrader output
Fetching results...