답안 #39626

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
39626	2018-01-16T19:18:22 Z	Hassoony	Retro (COCI17_retro)	C++14	0 / 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],open1,add;
pair<char,int>pp;
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;
    pair<int,char>v[5];
    v[3]={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+1,v+4);
    for(int i=1;i<=3;i++){
        pp=v[i];
        open1=open,add=0;
        if(pp.first=='(')open1++;
        if(pp.first==')')open1--,add=2;
        if(pp.first=='('||pp.first==')')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];
    pair<int,char>v[5];
    v[3]={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+1,v+4);
    for(int i=0;i<3;i++){
        pp=v[i];
        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(){
    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:65: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:76:19: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
     cout<<DP(n,j,0)<<endl;
                   ^

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	9 ms	117360 KB	Unexpected end of file - token expected
2	Incorrect	9 ms	117360 KB	Output isn't correct
3	Incorrect	16 ms	117360 KB	Unexpected end of file - token expected
4	Incorrect	0 ms	117360 KB	Output isn't correct
5	Incorrect	6 ms	117360 KB	Output isn't correct
6	Execution timed out	500 ms	117360 KB	Execution timed out
7	Execution timed out	500 ms	117360 KB	Execution timed out
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	Incorrect	16 ms	117360 KB	Integer -1 violates the range [1, 100000]
12	Incorrect	13 ms	117360 KB	Integer -1 violates the range [1, 100000]
13	Execution timed out	500 ms	117360 KB	Execution timed out
14	Execution timed out	500 ms	117360 KB	Execution timed out
15	Incorrect	16 ms	117360 KB	Integer -1 violates the range [1, 100000]
16	Incorrect	23 ms	117360 KB	Integer -1 violates the range [1, 100000]
17	Execution timed out	500 ms	117360 KB	Execution timed out
18	Execution timed out	500 ms	117360 KB	Execution timed out
19	Incorrect	13 ms	117360 KB	Integer -1 violates the range [1, 100000]
20	Incorrect	6 ms	117360 KB	Integer -1 violates the range [1, 100000]