Submission #40116

#	Time	Username	Problem	Language	Result	Execution time	Memory
40116		Chomtana	Retro (COCI17_retro)	C++11	40 / 100	209 ms	113668 KiB

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 (stderr)

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 / 100