답안 #40117

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
40117	2018-01-27T09:06:07 Z	Chomtana	Retro (COCI17_retro)	C++11	40 / 100	216 ms	2836 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 dpbu[305][305];
int dpbubf[305][305];
int sr,sc;

//bu must start at index 1 because it will out of border
int bu(int r,int c,int lv) {
    if (r<=0 || c<=0) {
        if (lv==0) {
            return 0;
        } else {
            return -999999;
        }
    }
    if (data[r-1][c-1]=='*') {
        return -999999;
    }
    
    if (data[r-1][c-1]!='(' && data[r-1][c-1]!=')') {
        return max(dpbubf[c-1][lv],dpbubf[c+1][lv],dpbubf[c][lv]);
    } else {
        if (data[r-1][c-1]=='(') {
            return max(dpbubf[c-1][lv+1]+1,dpbubf[c+1][lv+1]+1,dpbubf[c][lv+1]+1);
        } else {
            if (lv>0) {
                return max(dpbubf[c-1][lv-1]+1,dpbubf[c+1][lv-1]+1,dpbubf[c][lv-1]+1);
            } else {
                return -999999;
            }
        }
    }
}

/*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));
    memset(dpbu,-1,sizeof(dpbu));
    
    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;
            }
        }
    }
    
    for1(j,0,nc+2) {
        for1(k,0,305) {
            dpbubf[j][k] = bu(0,j,k);
            //if (k<=10) cerr<<dpbubf[j][k]<<' ';
        }
        //cerr<<endl;
    }
    //cerr<<endl;
    
    for(int i = 1;i<=sr+1;i++) {
        for1(j,0,nc+2) {
            for1(k,0,305) {
                dpbu[j][k] = bu(i,j,k);
            }
        }
        
        for1(j,0,nc+2) {
            for1(k,0,305) {
                //if (k<=10) cerr<<dpbu[j][k]<<' ';
                dpbubf[j][k] = dpbu[j][k];
            }
            //cerr<<endl;
        }
        //cerr<<endl;
    }
    
    int res = dpbu[sc+1][0];
    //int res = f(sr,sc,0);
    
    /*f(sr,sc,0);
    for(int i = 0;i<=sr;i++) {
        for1(j,0,nc) {
            for1(k,0,305) {
                if (k<=10) cerr<<dp[i][j][k]<<' ';
            }
            cerr<<endl;
        }
        cerr<<endl;
    }*/
    
    
    cout<<res<<endl;
    for1(i,0,res/2) {
        printf("()");
    }
    return 0;
}

Compilation message

retro.cpp: In function 'int main()':
retro.cpp:98: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	1 ms	2836 KB	Partially correct
2	Partially correct	0 ms	2836 KB	Partially correct
3	Partially correct	1 ms	2836 KB	Partially correct
4	Partially correct	0 ms	2836 KB	Partially correct
5	Partially correct	2 ms	2836 KB	Partially correct
6	Partially correct	10 ms	2836 KB	Partially correct
7	Partially correct	15 ms	2836 KB	Partially correct
8	Partially correct	7 ms	2836 KB	Partially correct
9	Partially correct	32 ms	2836 KB	Partially correct
10	Partially correct	30 ms	2836 KB	Partially correct
11	Partially correct	176 ms	2836 KB	Partially correct
12	Partially correct	206 ms	2836 KB	Partially correct
13	Partially correct	92 ms	2836 KB	Partially correct
14	Partially correct	79 ms	2836 KB	Partially correct
15	Partially correct	182 ms	2836 KB	Partially correct
16	Partially correct	180 ms	2836 KB	Partially correct
17	Partially correct	171 ms	2836 KB	Partially correct
18	Partially correct	154 ms	2836 KB	Partially correct
19	Partially correct	216 ms	2836 KB	Partially correct
20	Partially correct	185 ms	2836 KB	Partially correct