Submission #471273

#	Time	Username	Problem	Language	Result	Execution time	Memory
471273		clams	Knapsack (NOI18_knapsack)	C++17	100 / 100	125 ms	35140 KiB

knapsack

/*
 * Author: bubu2006
**/

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    ll limit, n;
    cin >> limit >> n;
    
    // since limit <= 1000 and W[i] <= limit -> we can group items by weight
    map<int, vector<pair<int, int>>> weight;
    for(int i = 0; i < n; i++) {
       int val, w, cnt;
       cin >> val >> w >> cnt;
       if(w <= limit && cnt >= 1) {
           weight[w].push_back({val, cnt});
       }
    }
    
    int sz = weight.size();
    vector<vector<ll>> dp(sz + 1, vector<ll>(limit + 1, INT_MIN));
    dp[0][0] = 0;
    
    int index = 1;
    for(auto& [w, items] : weight) {
        // sort items by value
        sort(items.rbegin(), items.rend());
        
        for(int curlimit = 0; curlimit <= limit; curlimit++) {
            // if can reach sum with s using index - 1 then can reach with index
            dp[index][curlimit] = dp[index - 1][curlimit];
            
            int copies = 0; // the current number of copies with weight "w"
            int curtype = 0; // current type we are considering
            int curused = 0; // count the number of used item of curtype
            ll profit = 0; // the current profit
            
            while((copies + 1) * w <= curlimit && curtype < (int)items.size()) {
                copies++;
                profit += items[curtype].first;
                
                if(dp[index - 1][curlimit - copies * w] != INT_MIN) {
                    dp[index][curlimit] = max(dp[index][curlimit], dp[index - 1][curlimit - copies * w] + profit);
                }
                
                curused++;
                if(curused == items[curtype].second) { // used all items of this value
                    curtype++; // move to the next type
                    curused = 0;
                }
            }
        }
        
        index++;
    }
    
    cout << *max_element(dp.back().begin(), dp.back().end()) << '\n';
}

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