답안 #40101

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
40101	2018-01-27T07:47:07 Z	Chomtana	Retro (COCI17_retro)	C++11	40 / 100	210 ms	112940 KB

retro

/*
This is a dag graph -> DP!!! let see ... it move only in one direction from bottom to top
Graph will be DAG if it move in one direction in all plane (dimension-1 dimension)
*/

#include <bits/stdc++.h>

#define for1(a,b,c) for(int (a)=(b);(a)<(c);(a)++)
#define for2(i,a,b) for(int (i)=(a);((a)<=(b)?(i)<=(b):(i)>=(b));(i)+=((a)<=(b)?1:-1))
#define until(x) while(!(x))
#define all(x) x.begin(),x.end()
#define mp make_pair
#define subfunc(ret,name,args) function<ret args> name; name = [&] args

#define max(a,b,c) max(max(a,b),c)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<pair<int,int>,int> piii;
typedef vector<int> vi;

int nr,nc;

char data[305][305];
int dp[305][305][305];
int sr,sc;

int f(int r,int c,int lv) {
    if (r<0 || c<0) {
        if (lv==0) {
            return 0;
        } else {
            return -999999;
        }
    }
    if (data[r][c]=='*') {
        return -999999;
    }
    
    if (dp[r][c][lv]!=-1) return dp[r][c][lv];
    
    if (data[r][c]!='(' && data[r][c]!=')') {
        return dp[r][c][lv] = max(f(r-1,c-1,lv),f(r-1,c+1,lv),f(r-1,c,lv));
    } else {
        if (data[r][c]=='(') {
            return dp[r][c][lv] = max(f(r-1,c-1,lv+1)+1,f(r-1,c+1,lv+1)+1,f(r-1,c,lv+1)+1);
        } else {
            if (lv>0) {
                return dp[r][c][lv] = max(f(r-1,c-1,lv-1)+1,f(r-1,c+1,lv-1)+1,f(r-1,c,lv-1)+1);
            } else {
                return dp[r][c][lv] = -999999;
            }
        }
    }
}

int main() {
    //ios::sync_with_stdio(false);
    memset(dp,-1,sizeof(dp));
    
    cout<<fixed;
    cin>>nr>>nc;
    for1(i,0,nr) {
        scanf("%s",data[i]);
    }
    
    for1(i,0,nr) {
        for1(j,0,nc) {
            if (data[i][j]=='M') {
                sr = i; sc=j;
            }
        }
    }
    
    int res = f(sr,sc,0);
    
    cout<<res<<endl;
    for1(i,0,res/2) {
        printf("()");
    }
    return 0;
}

Compilation message

retro.cpp: In function 'int main()':
retro.cpp:67:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",data[i]);
                            ^

Subtask #1

40.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	16 ms	112940 KB	Partially correct
2	Partially correct	3 ms	112940 KB	Partially correct
3	Partially correct	13 ms	112940 KB	Partially correct
4	Partially correct	3 ms	112940 KB	Partially correct
5	Partially correct	9 ms	112940 KB	Partially correct
6	Partially correct	10 ms	112940 KB	Partially correct
7	Partially correct	20 ms	112940 KB	Partially correct
8	Partially correct	13 ms	112940 KB	Partially correct
9	Partially correct	13 ms	112940 KB	Partially correct
10	Partially correct	17 ms	112940 KB	Partially correct
11	Partially correct	150 ms	112940 KB	Partially correct
12	Partially correct	136 ms	112940 KB	Partially correct
13	Partially correct	102 ms	112940 KB	Partially correct
14	Partially correct	95 ms	112940 KB	Partially correct
15	Partially correct	210 ms	112940 KB	Partially correct
16	Partially correct	160 ms	112940 KB	Partially correct
17	Partially correct	174 ms	112940 KB	Partially correct
18	Partially correct	133 ms	112940 KB	Partially correct
19	Partially correct	202 ms	112940 KB	Partially correct
20	Partially correct	181 ms	112940 KB	Partially correct