#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define a3 array<int, 3>
using namespace std;
const int N = 310;
const int oo = 2e9;
string ans = "", f[2][N][N], t;
char s[N][N];
int n, m, ff[2][N][N], an = 0;
bool better(string &nw, string &old){
return (sz(nw) > sz(old) || (sz(nw) == sz(old) && nw < old));
}
void upd(int &x, int y){
x = max(x, y);
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef _LOCAL
freopen("in.txt","r",stdin);
#endif // _LOCAL
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> s[n - 1 - i][j];
if (n > 100) {
for (int j = 0; j < m; j++)
if (s[0][j] == 'M')
ff[0][j][0] = 0;
else ff[0][j][0] = -1;
for (int i = 0, tp = 0; i < n - 1; i++, tp ^= 1){
for (int j = 0; j < m; j++)
for (int sm = 0; sm <= i + 1; sm++)
ff[tp ^ 1][j][sm] = -1;
for (int j = 0; j < m; j++)
for (int sm = 0; sm <= i; sm++){
if (ff[tp][j][sm] == -1) continue;
for (int stp = -1; stp < 2; stp++){
int ni = i + 1, nj = j + stp;
if (nj < 0 || nj >= m) continue;
if (s[ni][nj] == '*'){
if (sm == 0){
an = max(an, ff[tp][j][sm]);
}
} else if (s[ni][nj] == '.'){
upd(ff[tp ^ 1][nj][sm], ff[tp][j][sm]);
} else if (s[ni][nj] == '('){
upd(ff[tp ^ 1][nj][sm + 1], ff[tp][j][sm] + 1);
} else if (s[ni][nj] == ')'){
if (sm == 0) continue;
upd(ff[tp ^ 1][nj][sm - 1], ff[tp][j][sm] + 1);
}
}
}
}
int tp = (n - 1) % 2;
for (int j = 0; j < m; j++)
upd(an, ff[tp][j][0]);
cout << an << '\n';
for (int i = 0; i < an / 2; i++)
cout << "()";
} else {
for (int j = 0; j < m; j++)
if (s[0][j] == 'M')
f[0][j][0] = "";
else f[0][j][0] = ")";
for (int i = 0, tp = 0; i < n - 1; i++, tp ^= 1){
for (int j = 0; j < m; j++)
for (int sm = 0; sm <= i + 1; sm++)
f[tp ^ 1][j][sm] = ")";
for (int j = 0; j < m; j++)
for (int sm = 0; sm <= i; sm++){
if (f[tp][j][sm] == ")") continue;
for (int stp = -1; stp < 2; stp++){
int ni = i + 1, nj = j + stp;
if (nj < 0 || nj >= m) continue;
if (s[ni][nj] == '*'){
if (sm == 0){
if (better(f[tp][j][sm], ans))
ans = f[tp][j][sm];
}
} else if (s[ni][nj] == '.'){
if (f[tp ^ 1][nj][sm] == ")" || better(f[tp][j][sm], f[tp ^ 1][nj][sm]))
f[tp ^ 1][nj][sm] = f[tp][j][sm];
} else if (s[ni][nj] == '('){
t = f[tp][j][sm] + "(";
if (f[tp ^ 1][nj][sm + 1] == ")" || better(t, f[tp ^ 1][nj][sm + 1]))
f[tp ^ 1][nj][sm + 1] = t;
} else if (s[ni][nj] == ')'){
if (sm == 0) continue;
t = f[tp][j][sm] + ")";
// cerr << t << '\n' << f[tp ^ 1][nj][sm - 1] << '\n';
if (f[tp ^ 1][nj][sm - 1] == ")" || better(t, f[tp ^ 1][nj][sm - 1]))
f[tp ^ 1][nj][sm - 1] = t;
}
}
}
}
int tp = (n - 1) % 2;
for (int j = 0; j < m; j++)
if (f[tp][j][0] != ")" && better(f[tp][j][0], ans))
ans = f[tp][j][0];
cout << sz(ans) << '\n' << ans;
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
6400 KB |
Output is correct |
| 2 |
Correct |
8 ms |
6400 KB |
Output is correct |
| 3 |
Correct |
8 ms |
6400 KB |
Output is correct |
| 4 |
Correct |
8 ms |
6400 KB |
Output is correct |
| 5 |
Correct |
8 ms |
6400 KB |
Output is correct |
| 6 |
Correct |
18 ms |
6656 KB |
Output is correct |
| 7 |
Correct |
21 ms |
6656 KB |
Output is correct |
| 8 |
Correct |
16 ms |
6528 KB |
Output is correct |
| 9 |
Correct |
29 ms |
6784 KB |
Output is correct |
| 10 |
Correct |
32 ms |
6912 KB |
Output is correct |
| 11 |
Partially correct |
46 ms |
7168 KB |
Partially correct |
| 12 |
Partially correct |
42 ms |
7168 KB |
Partially correct |
| 13 |
Partially correct |
26 ms |
6784 KB |
Partially correct |
| 14 |
Partially correct |
25 ms |
6784 KB |
Partially correct |
| 15 |
Partially correct |
54 ms |
7288 KB |
Partially correct |
| 16 |
Partially correct |
48 ms |
7168 KB |
Partially correct |
| 17 |
Partially correct |
45 ms |
7040 KB |
Partially correct |
| 18 |
Partially correct |
42 ms |
7040 KB |
Partially correct |
| 19 |
Partially correct |
53 ms |
7168 KB |
Partially correct |
| 20 |
Partially correct |
47 ms |
7168 KB |
Partially correct |
