Submission #994558

#	Time	Username	Problem	Language	Result	Execution time	Memory
994558		a5a7	Knapsack (NOI18_knapsack)	C++14	100 / 100	97 ms	3696 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> 
using indexedset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;

int main(){
    int s, n;
    cin >> s >> n;
    vector<int> val(s+1, -1);
    vector<vector<pair<int, int>>> weights(s+1);
    val[0] = 0;
    for (int i = 0; i < n; i++){
        int v, w, k;
        cin >> v >> w >> k;
        weights[w].push_back({v, k});
    }
    for (int i = 0; i <= s; i++) sort(weights[i].begin(), weights[i].end(), greater<pair<int, int>>());
    for (int i = 0; i <= s; i++){
        if (weights[i].size() == 0) continue;
        for (int j = s; j > -1; j--){
            int value = 0;
            int ptr = 0;
            int curr = weights[i][ptr].second;
            for (int x = 1; x * i <= j && ptr < weights[i].size(); x++){
                value += weights[i][ptr].first;
                curr--;
                if (curr == 0) ptr++, curr = weights[i].size() == ptr ? 0 : weights[i][ptr].second;
                if (val[j-x*i] == -1) continue;
                val[j] = max(val[j-x*i]+value, val[j]);
            }
        }    
    }
    cout << (*max_element(val.begin(), val.end())) << endl;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:27:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |             for (int x = 1; x * i <= j && ptr < weights[i].size(); x++){
      |                                           ~~~~^~~~~~~~~~~~~~~~~~~
knapsack.cpp:30:64: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |                 if (curr == 0) ptr++, curr = weights[i].size() == ptr ? 0 : weights[i][ptr].second;
      |                                              ~~~~~~~~~~~~~~~~~~^~~~~~

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