oj.uz

Submission #40101

# Submission time Handle Problem Language Result Execution time Memory
40101 2018-01-27T07:47:07 Z Chomtana Retro (COCI17_retro) C++11
40 / 100
 210 ms 112940 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 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

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