/*
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]);
^
| # |
결과 |
실행 시간 |
메모리 |
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 |
