Submission #1242497

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242497		menkh	Knapsack (NOI18_knapsack)	C++17	73 / 100	1093 ms	5264 KiB

knapsack

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

#define int long long
// #define ll long long

#define MAX 20005
vector<int> dp(MAX);
int S, n;

struct menkh {
    int value, weight, num; 
};

void solve() {
    cin >> S >> n;
    vector<menkh> items(n + 1);

    int maxWeight = 0;
    for (int i = 1; i <= n; i++) {
        cin >> items[i].value >> items[i].weight >> items[i].num;
        maxWeight = max(maxWeight, items[i].weight);
    }

    vector<pair<int, int>> group[maxWeight + 1];
    for (int i = 1; i <= n; i++) {
        group[items[i].weight].push_back({items[i].value, items[i].num});
    }

    for (int i = 1; i <= maxWeight; i++) {
        sort(group[i].begin(), group[i].end(), [](pair<int, int> &A, pair<int, int> &B) {
            return A.first > B.first;
        });
    }

    dp[0] = 0;
    for (int w = 1; w <= maxWeight; w++) {
        if (group[w].empty()) continue;
        vector<int> old_dp = dp;

        for (pair<int, int> cur : group[w]) {
            int value = cur.first;
            int num = min(S / w, cur.second);

            for (int k = 1; k <= num; k++) {
                for (int j = S; j >= k * w; j--) {
                    dp[j] = max(dp[j], old_dp[j - k * w] + k * value);
                }        
            }
            old_dp = dp;
        }
    }   

    cout << dp[S] << '\n'; 
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // int t; cin >> t; 
    while (t--) solve();
}

// 1 MB = 1000000 bytes
// 1 int = 4 bytes
// memory consumption: (sizeof(...)_int * 4) / 1000000

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