Submission #1150367

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150367		duyph	Knapsack (NOI18_knapsack)	C++20	100 / 100	48 ms	1872 KiB

knapsack

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

int main() {
    cin.tie(nullptr)->sync_with_stdio(0);

    int S, n;
    cin >> S >> n;

    // (w, v, k)
    vector<array<int, 3>> a(n + 1);
    for (int i = 1; i <= n; i++) {
    	cin >> a[i][1] >> a[i][0] >> a[i][2];
    }

    sort(a.begin() + 1, a.end(), [](auto u, auto v) -> bool {
    	return u[0] == v[0] ? u[1] > v[1] : u[0] < v[0];
    });

    vector<array<int, 3>> b(1);

    int cnt = 0, sum = 0, pre = -1;
   	for (int i = 1, j = 1; i <= n; i++) {
   		j = i;
   		if (a[i][0] != pre)
   			cnt = 0;
   		pre = a[i][0];

   		sum = 0;
   		while (j <= n && a[j][0] == a[i][0] && a[j][1] == a[i][1])
   			cnt += a[j][2], sum += a[j][2], j++;
   		j--;

   		b.push_back({a[i][0], a[i][1], min(sum, S / a[i][0])});

   		if (cnt < S / a[i][0]) {
   			i = j;
   			continue;
   		}

   		while (j <= n && a[j][0] == a[i][0])
   			j++;

   		i = j - 1;
   	}

   	int m = b.size() - 1;

   	vector<int> dp(S + 1, -2e9), predp = dp;
   	dp[0] = predp[0] = 0;

   	for (int i = 1; i <= m; i++) {
   		for (int k = 1; k <= b[i][2]; k++) {
   			for (int j = S; j >= k * b[i][0]; j--) {
   				dp[j] = max(dp[j], predp[j - k * b[i][0]] + k * b[i][1]);
   			}
   		}
   		predp = dp;
   	}

   	cout << *max_element(dp.begin(), dp.end());

    

    return 0;
}

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