Submission #471548

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

retro

#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

retro.c: In function 'main':
retro.c:27:57: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   27 |       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)
      |                                   ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
retro.c:29:75: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   29 |       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))
      |                                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
retro.c:31:79: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   31 |       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))
      |                                                     ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
retro.c:13:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
retro.c:18:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |   scanf("%s", s);
      |   ^~~~~~~~~~~~~~

Subtask #1

39.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	1 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	Partially correct	9 ms	1100 KB	Partially correct
7	Partially correct	15 ms	1484 KB	Partially correct
8	Partially correct	9 ms	716 KB	Partially correct
9	Partially correct	20 ms	1196 KB	Partially correct
10	Partially correct	27 ms	1560 KB	Partially correct
11	Execution timed out	613 ms	5820 KB	Time limit exceeded
12	Execution timed out	541 ms	5572 KB	Time limit exceeded
13	Partially correct	279 ms	2500 KB	Partially correct
14	Partially correct	245 ms	2412 KB	Partially correct
15	Execution timed out	679 ms	6204 KB	Time limit exceeded
16	Execution timed out	645 ms	5956 KB	Time limit exceeded
17	Execution timed out	563 ms	5124 KB	Time limit exceeded
18	Execution timed out	515 ms	4864 KB	Time limit exceeded
19	Execution timed out	687 ms	6216 KB	Time limit exceeded
20	Execution timed out	619 ms	5956 KB	Time limit exceeded