# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
471548 | rainboy | Retro (COCI17_retro) | C11 | 687 ms | 6216 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 << 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 << l % 60) == 0 ? '(' : ')');
printf("\n");
return 0;
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |