Submission #987028

#	Time	Username	Problem	Language	Result	Execution time	Memory
987028		shokal_kishan	Knapsack (NOI18_knapsack)	C++17	12 / 100	2 ms	432 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;

                int rm = j - wt;
                if (rm < weight) break;

                int max_items = rm / weight;
                int num_items = min(max_items, count);

                pr += num_items * value;
                wt += num_items * weight;
            }

            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: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27