Submission #667500

#	Time	Username	Problem	Language	Result	Execution time	Memory
667500		therealpain	Knapsack (NOI18_knapsack)	C++17	100 / 100	75 ms	4896 KiB

knapsack

#include <bits/stdc++.h> 
#define fi first 
#define se second
#define mp make_pair
#define getbit(x, i) (((x) >> (i)) & 1)
#define all(x) x.begin(), x.end()
#define TASK ""
 
using namespace std;
 
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
 
const long long inf = 1e18;
const int mod = 1e9 + 7;
const int N = 1e5 + 7;

int s, n, ans;
int dp[2006];
int v[N], w[N], k[N];
vector <int> a[2006];
vector <pair <int, int>> item[2006];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> s >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> v[i] >> w[i] >> k[i];
		item[w[i]].emplace_back(v[i], k[i]);
	}
	for (int i = 0; i <= s; ++i) sort(all(item[i]));
	memset(dp, -0x3f, sizeof dp);
	dp[0] = 0;
	for (int i = 1; i <= s; ++i) { 
		int lim = s / i;
		while (item[i].size() && lim > 0) {
			auto &[value, cnt] = item[i].back();
			if (cnt > 0) {
				cnt--; lim--;
				a[i].emplace_back(value);
			} else item[i].pop_back();
		}
	}
	for (int i = 1; i <= s; ++i) 
		for (int j : a[i]) for (int k = s; k >= i; --k) maxi(dp[k], dp[k - i] + j);
	for (int i = 1; i <= s; ++i) maxi(ans, dp[i]);
	cout << ans;
		

}

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