#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define f first
#define s second
const int N = 300;
pair<int,string> dp1[100][100][100];
string a[N];
int dp[300][300][301];
int pred[300][300][301];
int n,m;
int pos=0;
void Case1()
{
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
for (int c=0; c<300; c++) dp[i][j][c]=-1e9;
dp[0][pos][0]=0;
for (int i=0; i<n-1; i++)
{
for (int j=0; j<m; j++)
if (a[i][j]!='*')
for (int c=0; c<300; c++)
{
for (int c1=-1; c1<=1; c1++)
{
int j1=j+c1;
if (j1>-1 && j1<m)
{
if ((a[i+1][j1]!='(' && a[i+1][j1]!=')') && dp[i+1][j1][c]<dp[i][j][c]) dp[i+1][j1][c]=dp[i][j][c],pred[i+1][j1][c]=-c1;
if (a[i+1][j1]=='(' && dp[i+1][j1][c+1]<dp[i][j][c]+1) dp[i+1][j1][c+1]=dp[i][j][c]+1,pred[i+1][j1][c+1]=-c1;
if (a[i+1][j1]==')' && c>0 && dp[i+1][j1][c-1]<dp[i][j][c]+1) dp[i+1][j1][c-1]=dp[i][j][c]+1,pred[i+1][j1][c-1]=-c1;
}
}
}
}
int mx=0,x=0,y=0;
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
if (a[i][j]=='*' || i==n-1)
if (dp[i][j][0]>mx) mx=max(mx,dp[i][j][0]),x=i,y=j;
cout<<mx<<endl;
string s;
int bal=0;
while (x>0)
{
int upd=0;
if (a[x][y]=='(' || a[x][y]==')')
{
s+=a[x][y];
if (a[x][y]=='(') upd--;
else upd++;
}
y+=pred[x][y][bal];
bal+=upd;
x--;
}
reverse(s.begin(),s.end());
cout<<s;
}
void Case2()
{
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
for (int c=0; c<100; c++) dp1[i][j][c]={1e9,""};
dp1[0][pos][0]={0,""};
for (int i=0; i<n-1; i++)
{
for (int j=0; j<m; j++)
if (a[i][j]!='*')
for (int c=0; c<100; c++)
{
for (int c1=-1; c1<=1; c1++)
{
int j1=j+c1;
if (j1>-1 && j1<m)
{
if (a[i+1][j1]!='(' && a[i+1][j1]!=')') dp1[i+1][j1][c]=min(dp1[i+1][j1][c],dp1[i][j][c]);
if (a[i+1][j1]=='(' ) dp1[i+1][j1][c+1]=min(dp1[i+1][j1][c+1],{dp1[i][j][c].f-1,dp1[i][j][c].s+"("});
if (a[i+1][j1]==')' && c>0) dp1[i+1][j1][c-1]=min(dp1[i+1][j1][c-1],{dp1[i][j][c].f-1,dp1[i][j][c].s+")"});
}
}
}
}
pair<int,string> mx={0,""};
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
if (a[i][j]=='*' || i==n-1) mx=min(mx,dp1[i][j][0]);
cout<<-mx.f<<"\n"<<mx.s;
}
int main()
{
cin>>n>>m;
for (int i=0; i<n; i++) cin>>a[i];
reverse(a,a+n);
for (int j=0; j<m; j++)
if (a[0][j]=='M') pos=j;
if (n>100) Case1();
else Case2();
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
39424 KB |
Output is correct |
2 |
Correct |
31 ms |
39424 KB |
Output is correct |
3 |
Correct |
28 ms |
39520 KB |
Output is correct |
4 |
Correct |
29 ms |
39424 KB |
Output is correct |
5 |
Correct |
37 ms |
39424 KB |
Output is correct |
6 |
Correct |
93 ms |
54780 KB |
Output is correct |
7 |
Correct |
136 ms |
66168 KB |
Output is correct |
8 |
Correct |
72 ms |
51064 KB |
Output is correct |
9 |
Correct |
131 ms |
68984 KB |
Output is correct |
10 |
Correct |
181 ms |
80376 KB |
Output is correct |
11 |
Partially correct |
349 ms |
237560 KB |
Partially correct |
12 |
Partially correct |
307 ms |
237560 KB |
Partially correct |
13 |
Partially correct |
161 ms |
127612 KB |
Partially correct |
14 |
Partially correct |
152 ms |
127384 KB |
Partially correct |
15 |
Partially correct |
351 ms |
250496 KB |
Partially correct |
16 |
Partially correct |
344 ms |
250360 KB |
Partially correct |
17 |
Partially correct |
305 ms |
218360 KB |
Partially correct |
18 |
Partially correct |
289 ms |
218232 KB |
Partially correct |
19 |
Partially correct |
371 ms |
251128 KB |
Partially correct |
20 |
Partially correct |
345 ms |
251064 KB |
Partially correct |