제출 #1034747

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1034747		roimu	Knapsack (NOI18_knapsack)	C++14	100 / 100	92 ms	5648 KiB

knapsack

//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <limits>
#include <unordered_map>
#include <random>


using namespace std;

typedef long long LL;

const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

class p {
public:
	int w;
	LL v;
	int c;

	bool operator<(const p &y) {
		if (w == y.w) {
			return v>y.v;
		}

		return w < y.w;
	}
};

int main() {
	int s, n; cin >> s >> n;
	vector<p> a;
	for (int i = 0; i < n; i++) {
		int w; LL v; int c;
		cin >> v >> w >> c;
		c = min(c, s);
		a.push_back({ w,v,c });
	}

	sort(a.begin(), a.end());
	LL nw = -1; LL nc = 0;

	vector<pair<LL, LL>> items;
	for (int i = 0; i < n; i++) {
		if (a[i].w > nw) {
			nw = a[i].w;
			nc = (s + nw - 1) / nw;
		}

		for (int j = 0; j < a[i].c; j++) {
			if (nc == 0)break;
			items.push_back({ a[i].w,a[i].v });
			nc--;
		}
	}

	vector<LL> dp(s + 1, -1); dp[0] = 0;
	n = items.size();
	for (int i = 0; i < n; i++) {
		LL w = items[i].first;
		LL v = items[i].second;
		for (int j = s; j >= 0; j--) {
			if (j - w >= 0 and dp[j - w] != -1) {
				dp[j] = max(dp[j], dp[j - w] + v);
			}
		}
	}

	cout << *max_element(dp.begin(), dp.end()) << endl;
	return 0;
}

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