Submission #40113

#TimeUsernameProblemLanguageResultExecution timeMemory
40113ChomtanaRetro (COCI17_retro)C++11
14 / 100
149 ms113668 KiB
/* 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 (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]);
                            ^
#Verdict Execution timeMemoryGrader output
Fetching results...