# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
40117 | Chomtana | Retro (COCI17_retro) | C++11 | 216 ms | 2836 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
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)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |