#include <stdio.h>
#include <string.h>
#define N 300
#define M 300
int main() {
static char s[M + 1];
static int dp[M][N], dq[M][N];
static long long sp[M][N][5], sq[M][N][5];
int n, m, i, j, d, d_;
scanf("%d%d", &n, &m);
for (j = 0; j < m; j++)
for (d = 0; d < n; d++)
dp[j][d] = d == 0 ? 0 : -1;
for (i = 0; i < n; i++) {
scanf("%s", s);
for (j = 0; j < m; j++)
for (d = 0; d < n; d++) {
if (s[j] == '*')
dq[j][d] = d == 0 ? 0 : -1;
else {
d_ = s[j] == '.' || s[j] == 'M' ? d : (s[j] == '(' ? d + 1 : d - 1);
dq[j][d] = -1;
if (d_ >= 0 && d_ < n) {
if (dq[j][d] < dp[j][d_] || dq[j][d] == dp[j][d_] && memcmp(sq[j][d], sp[j][d_], sizeof sp[j][d_]) > 0)
dq[j][d] = dp[j][d_], memcpy(sq[j][d], sp[j][d_], sizeof sp[j][d_]);
if (j > 0 && (dq[j][d] < dp[j - 1][d_] || dq[j][d] == dp[j - 1][d_] && memcmp(sq[j][d], sp[j - 1][d_], sizeof sp[j - 1][d_]) > 0))
dq[j][d] = dp[j - 1][d_], memcpy(sq[j][d], sp[j - 1][d_], sizeof sp[j - 1][d_]);
if (j + 1 < m && (dq[j][d] < dp[j + 1][d_] || dq[j][d] == dp[j + 1][d_] && memcmp(sq[j][d], sp[j + 1][d_], sizeof sp[j + 1][d_]) > 0))
dq[j][d] = dp[j + 1][d_], memcpy(sq[j][d], sp[j + 1][d_], sizeof sp[j + 1][d_]);
}
if (dq[j][d] != -1 && (s[j] == '(' || s[j] == ')')) {
if (s[j] == ')')
sq[j][d][4 - dq[j][d] / 60] |= 1LL << 59 - dq[j][d] % 60;
dq[j][d]++;
}
}
}
for (j = 0; j < m; j++)
for (d = 0; d < n; d++) {
dp[j][d] = dq[j][d];
if (dq[j][d] != -1)
memcpy(sp[j][d], sq[j][d], sizeof sq[j][d]);
}
}
for (j = 0; j < m; j++)
if (s[j] == 'M') {
int l = dp[j][0];
printf("%d\n", l);
while (l--)
printf("%c", (sp[j][0][4 - l / 60] & 1LL << 59 - l % 60) == 0 ? '(' : ')');
printf("\n");
return 0;
}
return 0;
}
Compilation message
retro.c: In function 'main':
retro.c:27:57: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
27 | if (dq[j][d] < dp[j][d_] || dq[j][d] == dp[j][d_] && memcmp(sq[j][d], sp[j][d_], sizeof sp[j][d_]) > 0)
| ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
retro.c:29:75: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
29 | if (j > 0 && (dq[j][d] < dp[j - 1][d_] || dq[j][d] == dp[j - 1][d_] && memcmp(sq[j][d], sp[j - 1][d_], sizeof sp[j - 1][d_]) > 0))
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
retro.c:31:79: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
31 | if (j + 1 < m && (dq[j][d] < dp[j + 1][d_] || dq[j][d] == dp[j + 1][d_] && memcmp(sq[j][d], sp[j + 1][d_], sizeof sp[j + 1][d_]) > 0))
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
retro.c:36:49: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
36 | sq[j][d][4 - dq[j][d] / 60] |= 1LL << 59 - dq[j][d] % 60;
| ~~~^~~~~~~~~~~~~~~
retro.c:54:52: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
54 | printf("%c", (sp[j][0][4 - l / 60] & 1LL << 59 - l % 60) == 0 ? '(' : ')');
| ~~~^~~~~~~~
retro.c:13:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
13 | scanf("%d%d", &n, &m);
| ^~~~~~~~~~~~~~~~~~~~~
retro.c:18:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
18 | scanf("%s", s);
| ^~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Partially correct |
1 ms |
332 KB |
Partially correct |
| 2 |
Correct |
1 ms |
460 KB |
Output is correct |
| 3 |
Partially correct |
1 ms |
332 KB |
Partially correct |
| 4 |
Partially correct |
1 ms |
460 KB |
Partially correct |
| 5 |
Partially correct |
2 ms |
1356 KB |
Partially correct |
| 6 |
Partially correct |
9 ms |
1156 KB |
Partially correct |
| 7 |
Partially correct |
16 ms |
1460 KB |
Partially correct |
| 8 |
Partially correct |
9 ms |
712 KB |
Partially correct |
| 9 |
Partially correct |
20 ms |
1192 KB |
Partially correct |
| 10 |
Correct |
27 ms |
1564 KB |
Output is correct |
| 11 |
Execution timed out |
625 ms |
6004 KB |
Time limit exceeded |
| 12 |
Execution timed out |
551 ms |
5600 KB |
Time limit exceeded |
| 13 |
Partially correct |
274 ms |
2504 KB |
Partially correct |
| 14 |
Partially correct |
246 ms |
2396 KB |
Partially correct |
| 15 |
Execution timed out |
753 ms |
6200 KB |
Time limit exceeded |
| 16 |
Execution timed out |
680 ms |
6096 KB |
Time limit exceeded |
| 17 |
Execution timed out |
570 ms |
5112 KB |
Time limit exceeded |
| 18 |
Execution timed out |
517 ms |
4756 KB |
Time limit exceeded |
| 19 |
Execution timed out |
695 ms |
6192 KB |
Time limit exceeded |
| 20 |
Execution timed out |
632 ms |
6000 KB |
Time limit exceeded |
