#include<bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)
typedef long long ll;
typedef pair<int, int> point;
const int MAXN = 302;
int dp[MAXN][MAXN][MAXN];
bool ok[MAXN][MAXN][MAXN];
int n, m, len;
char a[MAXN][MAXN];
bool mogu[MAXN][MAXN];
unordered_map<int, unordered_map<int, unordered_map <int, string> > > bio;
point mirko;
string sol;
void construct(int x, int y, int diff){
if(ok[x][y][diff]) return;
//cout << x _ y _ diff << " banana\n";
ok[x][y][diff] = true;
int nx = x + 1;
int ny = y - 1;
int val = 0;
if(a[x][y] == '(') val = -1;
else if(a[x][y] == ')') val = 1;
REP(i, 3){
if(a[nx][ny] == '*' || ny < 0 || ny >= m || nx >= n){
ny ++;
continue;
}
//cout << dp[nx][ny][diff + val] + (int)(val != 0) _ dp[x][y][diff] _ val _ diff + val _ " aaaaa\n";
if(dp[nx][ny][diff + val] + (int)(val != 0) == dp[x][y][diff])
construct(nx, ny, diff + val);
ny ++;
}
}
struct state{
int x, y, diff, lx, ly, ldiff;
};
void bfs(){
queue <state> Q;
Q.push({mirko.first, mirko.second, 0, MAXN - 1, MAXN - 1, 0});
while(!Q.empty()){
state kord = Q.front();
Q.pop();
int x = kord.x, y = kord.y, diff = kord.diff;
int val = 0;
if(a[x][y] == '(') val = 1;
else if(a[x][y] == ')') val = -1;
diff += val;
//cout << x _ y _ diff _ " pls radi\n";
//cout << " good zivot \n";
if(!ok[x][y][diff] || x < 0 || y < 0 || y >= m) continue;
//cout << " usrani zivot\n";
if(sz(bio[x][y][diff])){
//cout << "why\n";
if(a[x][y] == '.' && sz(bio[kord.lx][kord.ly][kord.ldiff]) == sz(bio[x][y][diff]))
bio[x][y][diff] = min(bio[x][y][diff], bio[kord.lx][kord.ly][kord.ldiff]);
else if((a[x][y] == '(' || a[x][y] == ')') && sz(bio[kord.lx][kord.ly][kord.ldiff]) + 1 == sz(bio[x][y][diff]))
bio[x][y][diff] = min(bio[x][y][diff], bio[kord.lx][kord.ly][kord.ldiff] + a[x][y]);
}
else if(a[x][y] != '*'){
//cout << "zivote\n";
if(a[x][y] == '(' || a[x][y] == ')'){
bio[x][y][diff] = bio[kord.lx][kord.ly][kord.ldiff] + a[x][y];
//cout << bio[x][y][diff] << " alalaal\n";
}
else{
bio[x][y][diff] = bio[kord.lx][kord.ly][kord.ldiff];
// cout << x _ y _ diff << " troll je bol\n";
}
Q.push({x - 1, y - 1, diff, x, y, diff}); Q.push({x - 1, y, diff, x, y, diff}); Q.push({x - 1, y + 1, diff, x, y, diff});
}
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> m;
REP(i, n)
REP(j, m)
cin >> a[i][j];
REP(j, m)
if(a[n - 1][j] == 'M'){
mirko = point(n - 1, j);
break;
}
int y = mirko.second;
int bounds = 1;
for(int i = n - 2; i >= 0; --i){
mogu[i][y] = true;
for(int j = y + 1; j <= min(m - 1, y + bounds); ++j)
mogu[i][j] = true;
for(int j = y - 1; j >= max(0, y - bounds); --j)
mogu[i][j] = true;
bounds ++;
}
mogu[mirko.first][mirko.second] = true;
for(int i = n - 2; i >= 0; --i){
REP(k, n){
REP(j, m){
if(a[i][j] == '*' || !mogu[i][j]) continue;
int val1 = 0, val2 = 0, val3 = 0;
if(a[i][j] == '.'){
if(j) val1 = dp[i + 1][j - 1][k];
val2 = dp[i + 1][j][k];
if(j != m - 1) val3 = dp[i + 1][j + 1][k];
dp[i][j][k] = max( max(val1, val2), max(dp[i][j][k], val3));
}
else if(a[i][j] == '(' && k > 0){
if(k != 1){
if(j && dp[i + 1][j - 1][k - 1]) val1 = dp[i + 1][j - 1][k - 1] + 1;
if(dp[i + 1][j][k - 1]) val2 = dp[i + 1][j][k - 1] + 1;
if(j != m - 1 && dp[i + 1][j + 1][k - 1]) val3 = dp[i + 1][j + 1][k - 1] + 1;
}
else{
if(j) val1 = dp[i + 1][j - 1][k - 1] + 1;
val2 = dp[i + 1][j][k - 1] + 1;
if(j != m - 1) val3 = dp[i + 1][j + 1][k - 1] + 1;
}
dp[i][j][k] = max( max(val1, val2), max(dp[i][j][k], val3));
}
else if(a[i][j] == ')'){
if(k){
if(j && dp[i + 1][j - 1][k + 1]) val1 = dp[i + 1][j - 1][k + 1] + 1;
if(dp[i + 1][j][k + 1]) val2 = dp[i + 1][j][k + 1] + 1;
if(j != m - 1 && dp[i + 1][j + 1][k + 1]) val3 = dp[i + 1][j + 1][k + 1] + 1;
}
else{
if(j && dp[i + 1][j - 1][k + 1] % 2) val1 = dp[i + 1][j - 1][k + 1] + 1;
if(dp[i + 1][j][k + 1] % 2) val2 = dp[i + 1][j][k + 1] + 1;
if(j != m - 1 && dp[i + 1][j + 1][k + 1] % 2) val3 = dp[i + 1][j + 1][k + 1] + 1;
}
dp[i][j][k] = max( max(val1, val2), max(dp[i][j][k], val3));
}
}
}
REP(j, m)
len = max(len, dp[i][j][0]);
}
REP(i, n)
REP(j, m)
if(dp[i][j][0] == len){
construct(i, j, 0);
//cout << "sve " _ i _ j _ 0 << "\n";
}
REP(i, 301)
sol += ')';
bfs();
cout << len << "\n";
REP(i, n)
REP(j, n){
if(sz(bio[i][j][0]) == len){
sol = min(sol, bio[i][j][0]);
}
}
cout << sol;
/*REP(k, n){
REP(i, n){
REP(j, m)
cout << dp[i][j][k];
cout << "\n";
}
cout << "\n\n\n";
} */
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Partially correct |
3 ms |
720 KB |
Partially correct |
| 3 |
Correct |
3 ms |
720 KB |
Output is correct |
| 4 |
Correct |
3 ms |
928 KB |
Output is correct |
| 5 |
Partially correct |
3 ms |
988 KB |
Partially correct |
| 6 |
Partially correct |
12 ms |
6312 KB |
Partially correct |
| 7 |
Correct |
19 ms |
7084 KB |
Output is correct |
| 8 |
Partially correct |
15 ms |
7084 KB |
Partially correct |
| 9 |
Correct |
21 ms |
10664 KB |
Output is correct |
| 10 |
Partially correct |
29 ms |
12428 KB |
Partially correct |
| 11 |
Partially correct |
235 ms |
93484 KB |
Partially correct |
| 12 |
Correct |
276 ms |
93484 KB |
Output is correct |
| 13 |
Partially correct |
152 ms |
93484 KB |
Partially correct |
| 14 |
Correct |
146 ms |
93484 KB |
Output is correct |
| 15 |
Partially correct |
341 ms |
104380 KB |
Partially correct |
| 16 |
Incorrect |
255 ms |
104380 KB |
Output isn't correct |
| 17 |
Partially correct |
263 ms |
104380 KB |
Partially correct |
| 18 |
Correct |
232 ms |
104380 KB |
Output is correct |
| 19 |
Correct |
274 ms |
104380 KB |
Output is correct |
| 20 |
Partially correct |
278 ms |
104380 KB |
Partially correct |
