oj.uz

Submission #39633

# Submission time Handle Problem Language Result Execution time Memory
39633 2018-01-16T19:38:43 Z Hassoony Retro (COCI17_retro) C++14
49 / 100
 406 ms 59736 KB 
#include<bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const short int inf=1000;
const short int MX=309;
char a[MX][MX];
short int n,m,dp[MX][MX][MX];
short int DP(short int x,short int y,short int open){
    if(y<0||y>=m||open<0)return -inf;
    if(x==0){
        if(open)return -inf;
        return 0;
    }
    if(a[x][y]=='*'){
        if(open)return -inf;
        return 0;
    }
    short int &ret=dp[x][y][open];if(ret!=-1)return ret;ret=-inf;
    pair<char,short int>v[3];
    if(y!=0)v[0]={a[x-1][y-1],y-1};
    v[1]={a[x-1][y],y};
    v[2]={a[x-1][y+1],y+1};
    sort(v,v+3);
    for(short int i=0;i<3;i++){
        pair<char,short int>pp=v[i];
        short int open1=open,add=0;
        if(pp.first=='(')open1++;
        if(pp.first==')')open1--,add=2;
        if((pp.first=='('||pp.first==')'))ret=max(ret,(short int)(DP(x-1,pp.second,open1)+add));
        ret=max(ret,DP(x-1,pp.second,open));
    }
    return ret;
}
void FDP(short int x,short int y,short int open){
    if(y<0||y>=m||open<0)return;
    if(x<=0)return;
    if(a[x][y]=='*')return;
    short int &ret=dp[x][y][open];
    pair<char,short int>v[3];
    if(y!=0)v[0]={a[x-1][y-1],y-1};
    v[1]={a[x-1][y],y};
    v[2]={a[x-1][y+1],y+1};
    sort(v,v+3);
    for(short int i=0;i<3;i++){
        pair<char,short int>pp=v[i];
        short int open1=open,add=0;
        if(pp.first=='(')open1++;
        if(pp.first==')')open1--,add=2;
        if(pp.first=='('||pp.first==')')if(ret==DP(x-1,pp.second,open1)+add){
            printf("%c",pp.first);
            FDP(x-1,pp.second,open1);
            return;
        }
        if(ret==DP(x-1,pp.second,open)){
            FDP(x-1,pp.second,open);
            return;
        }
    }
}
int main(){
    cin>>n>>m;
    for(short int i=1;i<=n;i++)scanf("%s",&a[i]);
    memset(dp,-1,sizeof(dp));
    short int j;
    for(short int i=0;i<m;i++){
        if(a[n][i]=='M')j=i;
    }
    cout<<DP(n,j,0)<<endl;
    FDP(n,j,0);
    puts("");
}

Compilation message

retro.cpp: In function 'int main()':
retro.cpp:65:48: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[309]' [-Wformat=]
     for(short int i=1;i<=n;i++)scanf("%s",&a[i]);
                                                ^
retro.cpp:65:49: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(short int i=1;i<=n;i++)scanf("%s",&a[i]);
                                                 ^
retro.cpp:67:15: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
     short int j;
               ^

Subtask #1
49.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 59736 KB Partially correct
2 Correct 9 ms 59736 KB Output is correct
3 Partially correct 3 ms 59736 KB Partially correct
4 Partially correct 3 ms 59736 KB Partially correct
5 Correct 0 ms 59736 KB Output is correct
6 Partially correct 9 ms 59736 KB Partially correct
7 Partially correct 6 ms 59736 KB Partially correct
8 Partially correct 6 ms 59736 KB Partially correct
9 Correct 13 ms 59736 KB Output is correct
10 Partially correct 9 ms 59736 KB Partially correct
11 Partially correct 279 ms 59736 KB Partially correct
12 Partially correct 236 ms 59736 KB Partially correct
13 Partially correct 116 ms 59736 KB Partially correct
14 Partially correct 129 ms 59736 KB Partially correct
15 Partially correct 333 ms 59736 KB Partially correct
16 Partially correct 306 ms 59736 KB Partially correct
17 Partially correct 279 ms 59736 KB Partially correct
18 Partially correct 223 ms 59736 KB Partially correct
19 Partially correct 406 ms 59736 KB Partially correct
20 Partially correct 273 ms 59736 KB Partially correct