Submission #40142

#	Time	Username	Problem	Language	Result	Execution time	Memory
40142		tiger13084	Retro (COCI17_retro)	C++14	8 / 100	179 ms	226504 KiB

retro

#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,x,y);
    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:111:28: warning: too many arguments for format [-Wformat-extra-args]
     printf("%d\n",ans*2,x,y);
                            ^
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]

• Subtask 1: 8 / 100