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

go

#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--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

40.0 / 100.0

#	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