Submission #475192

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
475192	2021-09-21T11:58:19 Z	rainboy	Go (COCI18_go)	C	100 / 100	60 ms	29508 KB

go

#include <stdio.h>

#define N	100
#define T	2000

int max(int a, int b) { return a > b ? a : b; }

int main() {
	static int xxl[N + 1], xxr[N + 1], ttl[N + 1], ttr[N + 1], aal[N + 1], aar[N + 1], dp[N + 1][N + 1][T][2];
	int n, nl, nr, k, i, j, l, r, t, ans, tmp;

	scanf("%d%d%d", &n, &k, &n), k--;
	nl = nr = 0;
	while (n--) {
		int a;

		scanf("%d%d%d", &i, &a, &t), i--, t--;
		if (i < k)
			nl++, xxl[nl] = k - i, ttl[nl] = t, aal[nl] = a;
		else
			nr++, xxr[nr] = i - k, ttr[nr] = t, aar[nr] = a;
	}
	for (i = 1, j = nl; i < j; i++, j--) {
		tmp = xxl[i], xxl[i] = xxl[j], xxl[j] = tmp;
		tmp = ttl[i], ttl[i] = ttl[j], ttl[j] = tmp;
		tmp = aal[i], aal[i] = aal[j], aal[j] = tmp;
	}
	ans = 0;
	for (l = 0; l <= nl; l++)
		for (r = 0; r <= nr; r++)
			for (t = 0; t < T; t++) {
				if (l == 0 && r == 0)
					dp[l][r][t][0] = dp[l][r][t][1] = t == 0 ? 0 : -1;
				else {
					int t_;

					dp[l][r][t][0] = -1;
					if (l > 0) {
						if ((t_ = t - (xxl[l] - xxl[l - 1])) >= 0)
							dp[l][r][t][0] = max(dp[l][r][t][0], dp[l - 1][r][t_][0]);
						if ((t_ = t - (xxl[l] + xxr[r])) >= 0)
							dp[l][r][t][0] = max(dp[l][r][t][0], dp[l - 1][r][t_][1]);
						if (dp[l][r][t][0] != -1 && t <= ttl[l])
							dp[l][r][t][0] += aal[l];
					}
					dp[l][r][t][1] = -1;
					if (r > 0) {
						if ((t_ = t - (xxr[r] - xxr[r - 1])) >= 0)
							dp[l][r][t][1] = max(dp[l][r][t][1], dp[l][r - 1][t_][1]);
						if ((t_ = t - (xxr[r] + xxl[l])) >= 0)
							dp[l][r][t][1] = max(dp[l][r][t][1], dp[l][r - 1][t_][0]);
						if (dp[l][r][t][1] != -1 && t <= ttr[r])
							dp[l][r][t][1] += aar[r];
					}
				}
				ans = max(ans, max(dp[l][r][t][0], dp[l][r][t][1]));
			}
	printf("%d\n", ans);
	return 0;
}

Compilation message

go.c: In function 'main':
go.c:12:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |  scanf("%d%d%d", &n, &k, &n), k--;
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
go.c:17:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |   scanf("%d%d%d", &i, &a, &t), i--, t--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	588 KB	Output is correct
3	Correct	1 ms	460 KB	Output is correct
4	Correct	2 ms	1100 KB	Output is correct
5	Correct	16 ms	10316 KB	Output is correct
6	Correct	20 ms	11420 KB	Output is correct
7	Correct	30 ms	20180 KB	Output is correct
8	Correct	36 ms	24424 KB	Output is correct
9	Correct	60 ms	29508 KB	Output is correct
10	Correct	39 ms	25980 KB	Output is correct