답안 #40142

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
40142	2018-01-28T05:41:39 Z	tiger13084	Retro (COCI17_retro)	C++14	8 / 100	179 ms	226504 KB

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

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.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	0 ms	226504 KB	Output isn't correct
2	Incorrect	0 ms	226504 KB	Output isn't correct
3	Partially correct	0 ms	226504 KB	Partially correct
4	Incorrect	1 ms	226504 KB	Output isn't correct
5	Incorrect	0 ms	226504 KB	Output isn't correct
6	Incorrect	0 ms	226504 KB	Output isn't correct
7	Incorrect	9 ms	226504 KB	Output isn't correct
8	Partially correct	0 ms	226504 KB	Partially correct
9	Incorrect	13 ms	226504 KB	Output isn't correct
10	Incorrect	20 ms	226504 KB	Output isn't correct
11	Incorrect	159 ms	226504 KB	Output isn't correct
12	Incorrect	143 ms	226504 KB	Output isn't correct
13	Partially correct	81 ms	226504 KB	Partially correct
14	Incorrect	71 ms	226504 KB	Output isn't correct
15	Incorrect	173 ms	226504 KB	Output isn't correct
16	Incorrect	172 ms	226504 KB	Output isn't correct
17	Incorrect	154 ms	226504 KB	Output isn't correct
18	Incorrect	142 ms	226504 KB	Output isn't correct
19	Partially correct	154 ms	226504 KB	Partially correct
20	Incorrect	179 ms	226504 KB	Output isn't correct