oj.uz

Submission #40147

# Submission time Handle Problem Language Result Execution time Memory
40147 2018-01-28T08:47:11 Z tiger13084 Retro (COCI17_retro) C++14
8 / 100
 222 ms 226504 KB 
#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

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]

Subtask #1
8.0 / 100.0

# Verdict Execution time Memory 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 0 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 5 ms 226504 KB Output isn't correct
8 Partially correct 0 ms 226504 KB Partially correct
9 Incorrect 7 ms 226504 KB Output isn't correct
10 Incorrect 10 ms 226504 KB Output isn't correct
11 Incorrect 158 ms 226504 KB Output isn't correct
12 Incorrect 175 ms 226504 KB Output isn't correct
13 Partially correct 89 ms 226504 KB Partially correct
14 Incorrect 59 ms 226504 KB Output isn't correct
15 Incorrect 186 ms 226504 KB Output isn't correct
16 Incorrect 160 ms 226504 KB Output isn't correct
17 Incorrect 125 ms 226504 KB Output isn't correct
18 Incorrect 133 ms 226504 KB Output isn't correct
19 Partially correct 176 ms 226504 KB Partially correct
20 Incorrect 222 ms 226504 KB Output isn't correct