Submission #471550

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
471550	2021-09-09T17:45:28 Z	rainboy	Retro (COCI17_retro)	C	100 / 100	269 ms	4152 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 / 2 + 1], dq[M][N / 2 + 1];
	static long long sp[M][N / 2 + 1][5], sq[M][N / 2 + 1][5];
	int n, m, i, j, d, d_;
 
	scanf("%d%d", &n, &m);
	for (j = 0; j < m; j++)
		for (d = 0; d <= n / 2; 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 / 2; 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 / 2) {
						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 / 2; 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

100.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	1 ms	1228 KB	Output is correct
6	Correct	4 ms	972 KB	Output is correct
7	Correct	7 ms	1356 KB	Output is correct
8	Correct	4 ms	656 KB	Output is correct
9	Correct	12 ms	1096 KB	Output is correct
10	Correct	12 ms	1484 KB	Output is correct
11	Correct	237 ms	4088 KB	Output is correct
12	Correct	218 ms	4088 KB	Output is correct
13	Correct	106 ms	1780 KB	Output is correct
14	Correct	117 ms	1788 KB	Output is correct
15	Correct	264 ms	4144 KB	Output is correct
16	Correct	269 ms	4036 KB	Output is correct
17	Correct	235 ms	3532 KB	Output is correct
18	Correct	208 ms	3524 KB	Output is correct
19	Correct	268 ms	4120 KB	Output is correct
20	Correct	240 ms	4152 KB	Output is correct