Submission #1255769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255769		cybergiest	Knapsack (NOI18_knapsack)	C++20	37 / 100	1 ms	472 KiB

knapsack

// Problem: Minimizing Coins
// Contest: CSES - CSES Problem Set
// URL: https://cses.fi/problemset/task/1634
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
#define V vector
#define P pair
#define pb push_back
#define epb emplace_back
#define endll "\n"
 
namespace config {
	void io() {
		ios::sync_with_stdio(false);
	    cin.tie(nullptr);
	}
}

namespace solution {
	void main() {
		// we cant literally just push back every single copy for all K for an item
		// try to group them together?
		// no but then it might lead to innacurate knapsack logic later
		// bundle with binary decomposition?
		// so weight 13 = 1 + 4 + 8
		
		int weightLimit, n;
		cin >> weightLimit >> n;
		V<int> weights, values;
		for (int i = 0; i < n; i++) {
			int value, weight, quantity;
			cin >> value >> weight >> quantity;
			int power = 1;
			while (quantity > 0) {
				int chunk = min(power, quantity);
				quantity -= chunk;
				int newWeight = weight * chunk;
				int newValue = value * chunk;
				weights.pb(newWeight);
				values.pb(newValue);
				power <<= 1;
			}
		}
		
		// ok so now this is just a classical 0/1 knapsack
		
		// dp[i] is the most value for a certain weight limit i
		
		V<int> dp(weightLimit + 1, 0);
		
		// base case:
		// the most value for a weight limit of 0 would be 0
		// this is already there since I initialized the whole vector to 0s
		
		// outside loop: iterate over items
		const int numItems = weights.size();
		for (int item = 0; item < numItems; item++) {
			for (int currentWeightLimit = weightLimit; currentWeightLimit >= weights[item]; currentWeightLimit--) {
				dp[currentWeightLimit] = max(dp[currentWeightLimit], dp[currentWeightLimit - weights[item]] + values[item]);
			}
		}
		
		cout << dp[weightLimit] << endll;
	}
}

int main() {
	config::io();
	solution::main();
	return 0;
}

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