Submission #575096

#	Time	Username	Problem	Language	Result	Execution time	Memory
575096		SuchPigeon	Knapsack (NOI18_knapsack)	C++17	12 / 100	7 ms	632 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int LIM = 20000;
ll dp[2][LIM+1];

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int s, n;
	ll w,k;
	ll v;
	fill(dp[0], dp[0]+LIM+1, 0);

	cin >> s >> n;

	while(n--) {
		cin >> v >> w >> k;
		fill(dp[1], dp[1]+LIM+1, 0);
		memcpy(dp[1], dp[0], w);

		for(int j = w; j <= LIM; j++) {
			for(ll t = 1; t <= k; t++) {
				if(t*w > j) break;
				dp[1][j] = max({dp[1][j], dp[0][j-t*w]+t*v, dp[1][j-1]});
			}
		}
		memcpy(dp[0], dp[1], LIM+1);
	}

	cout << dp[0][s] << '\n';
}

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