#include <stdio.h>
#include <string.h>
#define N 300
#define M 300
int compare(long long *aa, long long *bb) {
int i;
for (i = 4; i >= 0; i--)
if (aa[i] != bb[i])
return aa[i] < bb[i] ? -1 : 1;
return 0;
}
int main() {
static char s[M + 1];
static int dp[M][N / 2 + 1], dq[M][N / 2 + 1];
static long long sp[M][N / 2 + 1][5], sq[M][N / 2 + 1][5];
int n, m, i, j, d, d_;
scanf("%d%d", &n, &m);
for (j = 0; j < m; j++)
for (d = 0; d <= n / 2; 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 / 2; 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 / 2) {
if (dq[j][d] < dp[j][d_] || dq[j][d] == dp[j][d_] && compare(sq[j][d], 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_] && compare(sq[j][d], 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_] && compare(sq[j][d], 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][dq[j][d] / 60] |= 1LL << dq[j][d] % 60;
dq[j][d]++;
}
}
}
for (j = 0; j < m; j++)
for (d = 0; d <= n / 2; 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][l / 60] & 1LL << l % 60) == 0 ? '(' : ')');
printf("\n");
return 0;
}
return 0;
}
Compilation message
retro.c: In function 'main':
retro.c:36:57: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
36 | if (dq[j][d] < dp[j][d_] || dq[j][d] == dp[j][d_] && compare(sq[j][d], sp[j][d_]) > 0)
| ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
retro.c:38:75: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
38 | if (j > 0 && (dq[j][d] < dp[j - 1][d_] || dq[j][d] == dp[j - 1][d_] && compare(sq[j][d], sp[j - 1][d_]) > 0))
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
retro.c:40:79: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
40 | if (j + 1 < m && (dq[j][d] < dp[j + 1][d_] || dq[j][d] == dp[j + 1][d_] && compare(sq[j][d], sp[j + 1][d_]) > 0))
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
retro.c:22:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
22 | scanf("%d%d", &n, &m);
| ^~~~~~~~~~~~~~~~~~~~~
retro.c:27:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
27 | scanf("%s", s);
| ^~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
460 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
460 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1228 KB |
Output is correct |
| 6 |
Correct |
4 ms |
972 KB |
Output is correct |
| 7 |
Correct |
7 ms |
1356 KB |
Output is correct |
| 8 |
Correct |
4 ms |
656 KB |
Output is correct |
| 9 |
Correct |
12 ms |
1096 KB |
Output is correct |
| 10 |
Correct |
12 ms |
1484 KB |
Output is correct |
| 11 |
Correct |
237 ms |
4088 KB |
Output is correct |
| 12 |
Correct |
218 ms |
4088 KB |
Output is correct |
| 13 |
Correct |
106 ms |
1780 KB |
Output is correct |
| 14 |
Correct |
117 ms |
1788 KB |
Output is correct |
| 15 |
Correct |
264 ms |
4144 KB |
Output is correct |
| 16 |
Correct |
269 ms |
4036 KB |
Output is correct |
| 17 |
Correct |
235 ms |
3532 KB |
Output is correct |
| 18 |
Correct |
208 ms |
3524 KB |
Output is correct |
| 19 |
Correct |
268 ms |
4120 KB |
Output is correct |
| 20 |
Correct |
240 ms |
4152 KB |
Output is correct |
