//#pragma gcc optimize("O2")
#include <bits/stdc++.h>
//#include<complex>
using namespace std;
//#define int long long
int n;int m;
string gr[510];
int dp[302][302][302];
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>gr[i];
gr[i]="*"+gr[i]+"*";
}
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
for(int k=0;k<=n;k++){
dp[i][j][k]=-1e6;
}
}
}
for(int i=1;i<=m;i++){
if(gr[1][i]==')'){
dp[1][i][1]=0;
}
if(gr[1][i]=='.'){
dp[1][i][0]=0;
}
}
for(int i=2;i<=n;i++){
for(int j=1;j<=m;j++){
for(int k=0;k<=i;k++){
if(gr[i][j]=='*'){continue;}
if(gr[i][j]=='.'||gr[i][j]=='M'){
dp[i][j][k]=max({dp[i][j][k],dp[i-1][j][k],dp[i-1][j-1][k],dp[i-1][j+1][k]});
}
if(gr[i][j]==')'&&k>=1){
dp[i][j][k]=max({dp[i][j][k],dp[i-1][j][k-1],dp[i-1][j-1][k-1],dp[i-1][j+1][k-1]});
}
if(gr[i][j]=='('){
dp[i][j][k]=max({dp[i][j][k],1+dp[i-1][j][k+1],1+dp[i-1][j-1][k+1],1+dp[i-1][j+1][k+1]});
}
}
}
}
int nw;
for(int i=1;i<=m;i++){
if(gr[n][i]=='M'){
nw=i;
}
}
cout<<dp[n][nw][0]*2<<"\n";
cout<<"()\n";return 0;
for(int k=0;k<=3;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<dp[i][j][k]<<" ";
}cout<<endl;
}cout<<endl;
}
}
Compilation message
retro.cpp: In function 'int main()':
retro.cpp:53:18: warning: 'nw' may be used uninitialized in this function [-Wmaybe-uninitialized]
53 | cout<<dp[n][nw][0]*2<<"\n";
| ~~~~~~~~~~~^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
1 ms |
4444 KB |
Partially correct |
2 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
3 |
Partially correct |
1 ms |
6492 KB |
Partially correct |
4 |
Partially correct |
1 ms |
6492 KB |
Partially correct |
5 |
Partially correct |
1 ms |
6492 KB |
Partially correct |
6 |
Partially correct |
4 ms |
25180 KB |
Partially correct |
7 |
Incorrect |
6 ms |
29292 KB |
Output isn't correct |
8 |
Incorrect |
5 ms |
35164 KB |
Output isn't correct |
9 |
Incorrect |
6 ms |
37468 KB |
Output isn't correct |
10 |
Partially correct |
7 ms |
37468 KB |
Partially correct |
11 |
Partially correct |
63 ms |
101388 KB |
Partially correct |
12 |
Partially correct |
52 ms |
101200 KB |
Partially correct |
13 |
Incorrect |
31 ms |
107396 KB |
Output isn't correct |
14 |
Incorrect |
30 ms |
107356 KB |
Output isn't correct |
15 |
Incorrect |
60 ms |
107552 KB |
Output isn't correct |
16 |
Incorrect |
61 ms |
107696 KB |
Output isn't correct |
17 |
Incorrect |
55 ms |
107992 KB |
Output isn't correct |
18 |
Partially correct |
50 ms |
107984 KB |
Partially correct |
19 |
Partially correct |
59 ms |
108112 KB |
Partially correct |
20 |
Partially correct |
61 ms |
108148 KB |
Partially correct |