답안 #39621

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
39621	2018-01-16T19:09:12 Z	Hassoony	Retro (COCI17_retro)	C++14	2 / 100	500 ms	117360 KB

retro

#include<bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int inf=(1<<30);
const int MX=309;
char a[MX][MX];
int n,m,dp[MX][MX][MX];
int DP(int x,int y,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;
    }
    int &ret=dp[x][y][open];if(ret!=-1)return ret;
    vector<pair<char,int> >v;
    v.push_back({a[x-1][y-1],y-1});
    v.push_back({a[x-1][y],y});
    v.push_back({a[x-1][y+1],y+1});
    sort(v.begin(),v.end());
    for(auto pp:v){
        int open1=open,add=0;
        if(pp.first=='(')open1++;
        if(pp.first==')')open1--,add=2;
        ret=max(ret,DP(x-1,pp.second,open1)+add);
        ret=max(ret,DP(x-1,pp.second,open));
    }
    return ret;
}
void FDP(int x,int y,int open){
    if(y<=0||y>m||open<0)return;
    if(x==0)return;
    if(a[x][y]=='*')return;
    int &ret=dp[x][y][open];
    vector<pair<char,int> >v;
    v.push_back({a[x-1][y-1],y-1});
    v.push_back({a[x-1][y],y});
    v.push_back({a[x-1][y+1],y+1});
    sort(v.begin(),v.end());
    for(auto pp:v){
        int open1=open,add=0;
        if(pp.first=='(')open1++;
        if(pp.first==')')open1--,add=2;
        if(ret==DP(x-1,pp.second,open1)+add){
            if(pp.first!='.'&&pp.first!='*')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(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    memset(dp,-1,sizeof(dp));
    int j;
    for(int i=1;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:62: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:73:19: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
     cout<<DP(n,j,0)<<endl;
                   ^

Subtask #1

2.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	16 ms	117360 KB	Partially correct
2	Incorrect	13 ms	117360 KB	Token "(())()()
3	Incorrect	6 ms	117360 KB	Token "()(()())
4	Incorrect	6 ms	117360 KB	Token "(((())))
5	Incorrect	13 ms	117360 KB	Token "()((()))()
6	Incorrect	116 ms	117360 KB	Token "()((()((())()()((()())))(())()()(()())))
7	Incorrect	489 ms	117360 KB	Token "((())(()(()(()))(())(()()())()))(()()())(())
8	Execution timed out	500 ms	117360 KB	Execution timed out
9	Execution timed out	500 ms	117360 KB	Execution timed out
10	Execution timed out	500 ms	117360 KB	Execution timed out
11	Execution timed out	500 ms	117360 KB	Execution timed out
12	Execution timed out	500 ms	117360 KB	Execution timed out
13	Execution timed out	500 ms	117360 KB	Execution timed out
14	Execution timed out	500 ms	117360 KB	Execution timed out
15	Execution timed out	500 ms	117360 KB	Execution timed out
16	Execution timed out	500 ms	117360 KB	Execution timed out
17	Execution timed out	500 ms	117360 KB	Execution timed out
18	Execution timed out	500 ms	117360 KB	Execution timed out
19	Execution timed out	500 ms	117360 KB	Execution timed out
20	Execution timed out	500 ms	117360 KB	Execution timed out