oj.uz

Submission #40117

# Submission time Handle Problem Language Result Execution time Memory
40117 2018-01-27T09:06:07 Z Chomtana Retro (COCI17_retro) C++11
40 / 100
 216 ms 2836 KB 
/*
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

# Verdict Execution time Memory 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