제출 #633149

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
633149		hfoliacots	Knapsack (NOI18_knapsack)	C++14	12 / 100	1 ms	212 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;
using vi = vector<int>;
using vd = vector<double>;
using vvi = vector<vi>;
using vvd = vector<vd>;
using ll = long long;

int main() {
	int s, n;
	cin >> s >> n;
	vvd a(n, vd(4));
	for (int i = 0; i < n; i++) {
		double v, w, k;
		cin >> v >> w >> k;
		a[i] = {w/v, -v, w, k};
	}
	sort(a.begin(), a.end());
	
	int ans = 0, t = 0, i = 0;
	while (i < n) {
		if (t + a[i][2] > s) {
			i++;
			continue;
		}
		//cout << a[i][2] << ' ' << a[i][1] << ' ' << a[i][0] << endl;
		ans += -a[i][1];
		t += a[i][2];
		a[i][3]--;
		if (a[i][3] == 0) i++;
	}
	
	cout << ans << endl;
}

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