Submission #643400

#	Time	Username	Problem	Language	Result	Execution time	Memory
643400		VISHNUCODE	Knapsack (NOI18_knapsack)	C++14	100 / 100	155 ms	35248 KiB

knapsack

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <climits>
using namespace std;
int main(){
    int limit; int N; cin >> limit >> N;
    // group by weights
    map<int,vector<pair<int,int> > > weight_groups; //value,amount
    for(int i = 0;i < N;i++){
        int value; int weight; int amt; cin >> value >> weight >> amt;
        if(amt > 0 && limit >= weight){
            weight_groups[weight].push_back(make_pair(value,amt));
        }
    }
    vector<vector<long long > > best(weight_groups.size()+1,vector<long long> (limit+1,INT_MIN));
    //best [i][j] = max value you can get choosing the first i weight groups and spending at most j money
    best[0][0] = 0;
    int i = 1;
    for(auto&[w,items] : weight_groups){
        //sort weight groups in reverse order cuz you want the best value if you have the same weight lol
        sort(items.begin(),items.end(),greater<pair<int,int> >());
        for(int j = 0;j <= limit;j++){
            best[i][j] = best[i-1][j];
            int kthcopy = 0;
            int typecounter = 0;
            int curr_used = 0;
            long long profit = 0;
            //keep picking till you run out of options or run out of weight
            while((kthcopy + 1)* w <= j && typecounter < items.size()){
                kthcopy++;
                profit += items[typecounter].first;
                if(best[i-1][j-(kthcopy*w)] != INT_MIN){
                    best[i][j] = max(best[i][j],best[i-1][j-(kthcopy*w)] + profit);
                }
                curr_used++;
                if(curr_used == items[typecounter].second){
                    curr_used = 0;
                    typecounter++;
                }
            }
        }
        i++;
    }
    cout << *std::max_element(best.back().begin(), best.back().end()) << endl;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:21:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |     for(auto&[w,items] : weight_groups){
      |              ^
knapsack.cpp:31:56: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |             while((kthcopy + 1)* w <= j && typecounter < items.size()){
      |                                            ~~~~~~~~~~~~^~~~~~~~~~~~~~

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