답안 #40116

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
40116	2018-01-27T09:04:49 Z	Chomtana	Retro (COCI17_retro)	C++11	40 / 100	209 ms	113668 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	19 ms	113668 KB	Partially correct
2	Partially correct	13 ms	113668 KB	Partially correct
3	Partially correct	6 ms	113668 KB	Partially correct
4	Partially correct	3 ms	113668 KB	Partially correct
5	Partially correct	13 ms	113668 KB	Partially correct
6	Partially correct	20 ms	113668 KB	Partially correct
7	Partially correct	24 ms	113668 KB	Partially correct
8	Partially correct	26 ms	113668 KB	Partially correct
9	Partially correct	17 ms	113668 KB	Partially correct
10	Partially correct	31 ms	113668 KB	Partially correct
11	Partially correct	184 ms	113668 KB	Partially correct
12	Partially correct	191 ms	113668 KB	Partially correct
13	Partially correct	88 ms	113668 KB	Partially correct
14	Partially correct	87 ms	113668 KB	Partially correct
15	Partially correct	190 ms	113668 KB	Partially correct
16	Partially correct	209 ms	113668 KB	Partially correct
17	Partially correct	181 ms	113668 KB	Partially correct
18	Partially correct	187 ms	113668 KB	Partially correct
19	Partially correct	208 ms	113668 KB	Partially correct
20	Partially correct	209 ms	113668 KB	Partially correct