oj.uz

Submission #40113

# Submission time Handle Problem Language Result Execution time Memory
40113 2018-01-27T08:36:45 Z Chomtana Retro (COCI17_retro) C++11
14 / 100
 149 ms 113668 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,sc+3) {
        for1(k,0,305) {
            dpbubf[j][k] = bu(0,j,k);
        }
    }
    
    for(int i = 1;i<=sr+1;i++) {
        for1(j,0,sc+3) {
            for1(k,0,305) {
                dpbu[j][k] = bu(i,j,k);
            }
        }
        
        for1(j,0,sc+3) {
            for1(k,0,305) {
                //cerr<<dpbu[j][k]<<' ';
                dpbubf[j][k] = dpbu[j][k];
            }
            //cerr<<endl;
        }
        //cerr<<endl;
    }
    
    int res = dpbu[sc+1][0];
    
    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
14.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 113668 KB Output isn't correct
2 Partially correct 16 ms 113668 KB Partially correct
3 Incorrect 0 ms 113668 KB Output isn't correct
4 Partially correct 3 ms 113668 KB Partially correct
5 Incorrect 13 ms 113668 KB Output isn't correct
6 Incorrect 12 ms 113668 KB Output isn't correct
7 Partially correct 24 ms 113668 KB Partially correct
8 Incorrect 13 ms 113668 KB Output isn't correct
9 Incorrect 13 ms 113668 KB Output isn't correct
10 Partially correct 23 ms 113668 KB Partially correct
11 Partially correct 135 ms 113668 KB Partially correct
12 Incorrect 97 ms 113668 KB Output isn't correct
13 Incorrect 42 ms 113668 KB Output isn't correct
14 Incorrect 30 ms 113668 KB Output isn't correct
15 Incorrect 149 ms 113668 KB Output isn't correct
16 Incorrect 149 ms 113668 KB Integer 0 violates the range [1, 100000]
17 Incorrect 83 ms 113668 KB Output isn't correct
18 Partially correct 85 ms 113668 KB Partially correct
19 Partially correct 120 ms 113668 KB Partially correct
20 Incorrect 99 ms 113668 KB Output isn't correct