Submission #639820

#	Time	Username	Problem	Language	Result	Execution time	Memory
639820		oseip	Knapsack (NOI18_knapsack)	C++17	0 / 100	1 ms	596 KiB

knapsack

// Source: https://usaco.guide/general/io

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

struct item{
	int V; //Value
	int W; //Weight
	int K; //Kuantity
};

int S, N, x, iten; //size, number of items
vector<pair<int,int>> items;  
vector<int> ans;
vector<int> kays;

int main() {
	cin >> S >> N;
	S++;
	items.resize(N); ans.resize(S); kays.resize(N);
	for (int i = 0; i < N; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		items[i].first = x; items[i].second = y; kays[i] = z;
	}
	vector<vector<int>> keys(S);
	for (int i = 0 ; i < S; i++) {
		for (int j = 0; j < N; j++) {
			keys[i].push_back(kays[j]);
		}
	}
	for (int i = 0; i < S; i++) {
		int x = 0; iten = -1;
		for (int j = 0; j < N; j++) {
			if (items[j].second > i) continue;
			if (keys[i-items[j].second][j] > 0) {
				x = max(x,ans[i-items[j].second] + items[j].first); 
				if (x == ans[i-items[j].second] + items[j].first) iten = j;
			}
		}
		keys[i] = keys[i-items[iten].second]; keys[i][iten]--;
		ans[i] = x;	
	}
	x = 0;
	for (int i : ans) {
		x = max(x,i);
	}
	cout << x << endl;
}

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