Submission #987038

#	Time	Username	Problem	Language	Result	Execution time	Memory
987038		shokal_kishan	Knapsack (NOI18_knapsack)	C++17	100 / 100	253 ms	5112 KiB

knapsack

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;
#define int long long

void solve() {
    int s, n;
    cin >> s >> n;
    unordered_map<int, vector<pair<int, int>>> mp;

    // Reading input
    for (int i = 0; i < n; i++) {
        int v, w, k;
        cin >> v >> w >> k;
        mp[w].push_back({v, k});
    }

    vector<int> dp(s + 1, 0);

    for (auto& w : mp) {
        int weight = w.first;
        auto& items = w.second;

        sort(items.begin(), items.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
            return a.first > b.first;  // Sort by value descending
        });

        for (int j = s; j >= 0; j--) {
            int pr = 0, wt = 0;

            for (auto& item : items) {
                int value = item.first;
                int count = item.second;
                for(int k=0;k<count;k++){
                    int rm = j - wt;
                    if (rm < weight) break;
                    wt+=weight;
                    pr+=value;
                    dp[j]=max(dp[j],dp[j-wt]+pr);
                }
            }

            
        }
    }

    cout << dp[s] << endl;
}

int32_t main() {
    int t = 1; // cin >> t;
    while (t--) solve();
    return 0;
}

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