제출 #1248477

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1248477		saipranaydeep	Knapsack (NOI18_knapsack)	C++20	100 / 100	50 ms	1864 KiB

knapsack

/* (: A Lazy Coder :) */

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int s, n;
    cin >> s >> n;
    map<int, vector<pair<int,int>>> mp;
    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, INT_MIN);
    dp[0] = 0;
    for(auto &[wt, vals] : mp) {
        sort(vals.begin(), vals.end(), greater<>());
        for(int sum = s; sum >= wt; sum--) {
            int ind = 0, taken = 0, currtake = 0, profit = 0;
            while(ind < vals.size() && (taken + 1) * wt <= sum) {
                taken++;
                currtake++; 
                profit += (vals[ind].first);
                if(dp[sum - taken * wt] != INT_MIN) dp[sum] = max(dp[sum], dp[sum - taken * wt] + profit);
                if(currtake == vals[ind].second) {
                    ind++;
                    currtake = 0;
                }
            }
        }
    }
    cout << *max_element(dp.begin(), dp.end()) << "\n";
}

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