# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
471546 | rainboy | Retro (COCI17_retro) | C11 | 1097 ms | 24424 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 compare(char *s, char *t, int l) {
while (l-- > 0)
if (s[l] != t[l])
return s[l] - t[l];
return 0;
}
int main() {
static char s[M + 1];
static int dp[M][N], dq[M][N];
static char sp[M][N][N + 1], sq[M][N][N + 1];
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_] && compare(sq[j][d], sp[j][d_], dq[j][d]) > 0)
dq[j][d] = dp[j][d_], memcpy(sq[j][d], sp[j][d_], dp[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_], dq[j][d]) > 0))
dq[j][d] = dp[j - 1][d_], memcpy(sq[j][d], sp[j - 1][d_], dp[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_], dq[j][d]) > 0))
dq[j][d] = dp[j + 1][d_], memcpy(sq[j][d], sp[j + 1][d_], dp[j + 1][d_] * sizeof *sp[j + 1][d_]);
}
if (dq[j][d] != -1 && s[j] != '.' && s[j] != 'M')
sq[j][d][dq[j][d]++] = s[j];
}
}
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], dq[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]);
printf("\n");
return 0;
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |