Submission #651581

#	Time	Username	Problem	Language	Result	Execution time	Memory
651581		ChasingClouds	Knapsack (NOI18_knapsack)	C++14	100 / 100	115 ms	5184 KiB

knapsack

/***AUTHOR: ChasingClouds***/

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

struct item {
    ll weight;
    ll worth;
    ll cnt;
};

bool comp (item it1, item it2) {
    if(it1.weight == it2.weight) return it1.worth > it2.worth;
    return it1.weight < it2.weight;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

    ll S, N; cin >> S >> N;

    vector<item> items;
    for(int i=0; i<N; i++) {
        ll v, w, cnt;
        cin >> v >> w >> cnt;
        items.push_back({w, v, cnt});
    }

    sort(items.begin(), items.end(), comp);

    vector<item> new_item;
    map<int,int> myMap;

    for(auto c: items) {
        if(myMap[c.weight] * c.weight > S) continue;
        myMap[c.weight] += c.cnt;
        new_item.push_back(c);
    }
    swap(new_item, items);

    ll dp[S+1];
   for(int i=0; i<=S; i++) dp[i]=0;

    ll myMax = 0;

    for(int i=1; i<=items.size(); i++) {
        for(int j=S; j>=0; j--) {
            int cntr = 0;
            while(cntr * items[i-1].weight <= j and cntr <= items[i-1].cnt){
                dp[j] = max(dp[j], dp[j - cntr * items[i-1].weight] + cntr * items[i-1].worth);
                cntr++;

            }

           myMax = max(myMax, dp[j]);
        }

    }
    cout << myMax << "\n";


	return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:47:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i=1; i<=items.size(); i++) {
      |                  ~^~~~~~~~~~~~~~

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