Submission #39633

#	Time	Username	Problem	Language	Result	Execution time	Memory
39633		Hassoony	Retro (COCI17_retro)	C++14	49 / 100	406 ms	59736 KiB

retro

#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 (stderr)

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 / 100