oj.uz

Submission #40142

# Submission time Handle Problem Language Result Execution time Memory
40142 2018-01-28T05:41:39 Z tiger13084 Retro (COCI17_retro) C++14
8 / 100
 179 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,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

# 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 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