Submission #471546

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
471546	2021-09-09T17:33:11 Z	rainboy	Retro (COCI17_retro)	C	60 / 100	500 ms	24424 KB

retro

#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

retro.c: In function 'main':
retro.c:34:57: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   34 |       if (dq[j][d] < dp[j][d_] || dq[j][d] == dp[j][d_] && compare(sq[j][d], sp[j][d_], dq[j][d]) > 0)
      |                                   ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
retro.c:36:75: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   36 |       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))
      |                                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
retro.c:38:79: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   38 |       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))
      |                                                     ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
retro.c:20:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
retro.c:25:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   scanf("%s", s);
      |   ^~~~~~~~~~~~~~

Subtask #1

60.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	1 ms	460 KB	Output is correct
3	Correct	0 ms	332 KB	Output is correct
4	Correct	1 ms	588 KB	Output is correct
5	Correct	2 ms	1612 KB	Output is correct
6	Correct	7 ms	2124 KB	Output is correct
7	Correct	12 ms	3048 KB	Output is correct
8	Correct	6 ms	1228 KB	Output is correct
9	Correct	17 ms	2508 KB	Output is correct
10	Correct	22 ms	3468 KB	Output is correct
11	Execution timed out	898 ms	21848 KB	Time limit exceeded
12	Execution timed out	766 ms	20592 KB	Time limit exceeded
13	Correct	305 ms	8900 KB	Output is correct
14	Correct	224 ms	8180 KB	Output is correct
15	Execution timed out	1097 ms	24424 KB	Time limit exceeded
16	Execution timed out	908 ms	23140 KB	Time limit exceeded
17	Execution timed out	884 ms	19700 KB	Time limit exceeded
18	Execution timed out	628 ms	17732 KB	Time limit exceeded
19	Execution timed out	1090 ms	24152 KB	Time limit exceeded
20	Execution timed out	887 ms	22888 KB	Time limit exceeded