Submission #898720

#	Time	Username	Problem	Language	Result	Execution time	Memory
898720		Amaarsaa	Knapsack (NOI18_knapsack)	C++14	12 / 100	1 ms	348 KiB

knapsack

#include<bits/stdc++.h>

using namespace std;
using ll = int;
const int N = 1e5 + 2;
ll weight[N], CanAdd[N], price[N], Left[N];
ll dp[3][2005];
int main() {
//	freopen("moocast.in", "r", stdin);
//	freopen("moocast.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	ll i, ans, j, r, last, now, n, k;

	cin >> k >> n;
	
	for (i = 1; i <= n; i ++) {
		cin >> price[i] >> weight[i] >> Left[i];
	}
	last = 1;
	now = 0;
	memset(dp, -0x3f, sizeof dp);
	ll R =dp[0][0];
	dp[0][0] = 0;
	for (i = 1; i <= n; i ++) {
		last ^= 1;
		now ^= 1;
//		cout << now << " " << last << endl;
		for (j = 0; j <= k; j ++) {
			dp[now][j] = max(dp[last][j], dp[now][j]);
			if ( dp[last][j] != R) CanAdd[j] = max(CanAdd[j], Left[i]);
			if ( CanAdd[j] != 0 && j + weight[i] <= k) {
			//	cout << i << "R" << j << endl;
				CanAdd[j + weight[i]] = max(CanAdd[j] - 1, CanAdd[j + weight[i]]);
				dp[now][j + weight[i]] = max(dp[now][j + weight[i]], dp[now][j] + price[i]);
			}
			CanAdd[j] = 0;
		//	cout << i << " " << j << " " << dp[now][j] << endl;
		}
	}
	ans = 0;
	for (i = 0; i <= k; i ++) {
		ans = max(ans, dp[now][i]);
	}
	cout << ans << endl;
	
		
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:13:16: warning: unused variable 'r' [-Wunused-variable]
   13 |  ll i, ans, j, r, last, now, n, k;
      |                ^

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