Submission #784029

#	Time	Username	Problem	Language	Result	Execution time	Memory
784029		rainboy	Knapsack (NOI18_knapsack)	C11	73 / 100	1066 ms	304 KiB

knapsack

#include <stdio.h>
#include <string.h>

#define M	2000

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

int main() {
	static int dp[M + 1], dq[M + 1], qu[M + 1];
	int n, m, r, s, ans, head, cnt;

	scanf("%d%d", &m, &n);
	memset(dp, -1, (m + 1) * sizeof *dp), dp[0] = 0;
	while (n--) {
		int v, w, k;

		scanf("%d%d%d", &v, &w, &k);
		if (w > m)
			continue;
		for (r = 0; r < w; r++) {
			head = cnt = 0;
			for (s = r; s <= m; s += w) {
				if (dp[s] != -1) {
					dq[s] = dp[s] - s / w * v;
					while (cnt && dq[qu[head + cnt - 1]] <= dq[s])
						cnt--;
					qu[head + cnt++] = s;
				}
				dp[s] = cnt == 0 ? -1 : dq[qu[head]] + s / w * v;
				if (cnt && (s - qu[head]) / w == k)
					head++, cnt--;
			}
		}
	}
	ans = 0;
	for (s = 0; s <= m; s++)
		ans = max(ans, dp[s]);
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 0 / 27