Submission #475051

# Submission time Handle Problem Language Result Execution time Memory
475051 2021-09-20T20:41:41 Z rainboy Go (COCI18_go) C
40 / 100
1000 ms 16460 KB
#include <stdio.h>

#define N	1000
#define T	2000

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

int main() {
	static int bb[N][T], dp[N][T][2];
	int n, k, m, i, l, r, t, ans;

	scanf("%d%d%d", &n, &k, &m), k--;
	while (m--) {
		int b;

		scanf("%d%d%d", &i, &b, &t), i--, t--;
		bb[i][t] += b;
	}
	for (i = 0; i < n; i++)
		for (t = T - 2; t >= 0; t--)
			bb[i][t] += bb[i][t + 1];
	ans = 0;
	for (l = k; l >= 0; l--)
		for (r = k; r < n; r++)
			for (t = T - 1; t >= 0; t--) {
				if (l == r)
					dp[r][t][0] = dp[r][t][1] = t == 0 ? bb[l][t] : -1;
				else {
					dp[r][t][0] = dp[r][t][1] = -1;
					if (t >= 1) {
						dp[r][t][0] = max(dp[r][t][0], dp[r][t - 1][0]);
						dp[r][t][1] = max(dp[r][t][1], dp[r - 1][t - 1][1]);
					}
					if (t >= r - l) {
						dp[r][t][0] = max(dp[r][t][0], dp[r][t - r - l][1]);
						dp[r][t][1] = max(dp[r][t][1], dp[r - 1][t - r - l][0]);
					}
					if (dp[r][t][0] != -1)
						dp[r][t][0] += bb[l][t];
					if (dp[r][t][1] != -1)
						dp[r][t][1] += bb[r][t];
				}
				ans = max(ans, max(dp[r][t][0], dp[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, &m), k--;
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
go.c:16:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |   scanf("%d%d%d", &i, &b, &t), i--, t--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 877 ms 7420 KB Output is correct
2 Incorrect 387 ms 6320 KB Output isn't correct
3 Correct 5 ms 1996 KB Output is correct
4 Correct 567 ms 10168 KB Output is correct
5 Incorrect 562 ms 5708 KB Output isn't correct
6 Correct 48 ms 2892 KB Output is correct
7 Execution timed out 1090 ms 13536 KB Time limit exceeded
8 Execution timed out 1097 ms 16460 KB Time limit exceeded
9 Incorrect 484 ms 7628 KB Output isn't correct
10 Execution timed out 1093 ms 16332 KB Time limit exceeded