Submission #471547

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
471547	2021-09-09T17:39:44 Z	rainboy	Retro (COCI17_retro)	C	75 / 100	500 ms	6372 KB

retro

#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], 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_] && 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; 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);
      |   ^~~~~~~~~~~~~~

Subtask #1

75.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	460 KB	Output is correct
5	Correct	2 ms	1356 KB	Output is correct
6	Correct	8 ms	1132 KB	Output is correct
7	Correct	14 ms	1456 KB	Output is correct
8	Correct	7 ms	716 KB	Output is correct
9	Correct	17 ms	1200 KB	Output is correct
10	Correct	23 ms	1528 KB	Output is correct
11	Execution timed out	507 ms	5828 KB	Time limit exceeded
12	Correct	490 ms	5572 KB	Output is correct
13	Correct	233 ms	2508 KB	Output is correct
14	Correct	210 ms	2400 KB	Output is correct
15	Execution timed out	582 ms	6212 KB	Time limit exceeded
16	Execution timed out	564 ms	5940 KB	Time limit exceeded
17	Correct	484 ms	5112 KB	Output is correct
18	Correct	447 ms	4940 KB	Output is correct
19	Execution timed out	606 ms	6372 KB	Time limit exceeded
20	Execution timed out	547 ms	5884 KB	Time limit exceeded