oj.uz

Submission #40148

# Submission time Handle Problem Language Result Execution time Memory
40148 2018-01-28T08:55:28 Z tiger13084 Retro (COCI17_retro) C++14
14 / 100
 203 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+1;
                }
            }
            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);
    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
14.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 226504 KB Partially correct
2 Partially correct 0 ms 226504 KB Partially correct
3 Partially correct 0 ms 226504 KB Partially correct
4 Incorrect 0 ms 226504 KB Output isn't correct
5 Partially correct 0 ms 226504 KB Partially correct
6 Incorrect 3 ms 226504 KB Output isn't correct
7 Incorrect 3 ms 226504 KB Output isn't correct
8 Partially correct 4 ms 226504 KB Partially correct
9 Incorrect 3 ms 226504 KB Output isn't correct
10 Incorrect 7 ms 226504 KB Output isn't correct
11 Incorrect 169 ms 226504 KB Output isn't correct
12 Incorrect 153 ms 226504 KB Output isn't correct
13 Partially correct 60 ms 226504 KB Partially correct
14 Incorrect 69 ms 226504 KB Output isn't correct
15 Incorrect 189 ms 226504 KB Output isn't correct
16 Incorrect 175 ms 226504 KB Output isn't correct
17 Incorrect 149 ms 226504 KB Output isn't correct
18 Incorrect 164 ms 226504 KB Output isn't correct
19 Partially correct 168 ms 226504 KB Partially correct
20 Incorrect 203 ms 226504 KB Output isn't correct