Submission #879114

#	Time	Username	Problem	Language	Result	Execution time	Memory
879114		AminMDNZ	Knapsack (NOI18_knapsack)	C++17	0 / 100	1 ms	348 KiB

knapsack

// #include<bits/stdc++.h>
// using namespace std;
// int n, s;
// vector<long long> dp;
// vector<int> v;
// vector<int> w;
// vector<int> k;

// int main(){
//     cin>>s>>n;
//     dp.assign(s+1, 0);
//     v.resize(n);
//     w.resize(n);
//     k.resize(n);
//     for(int i=0;i<n;i++) cin>>v[i]>>w[i]>>k[i];

//     dp[0] = 0;

//     for(int i=0;i<n;i++){
//         for(int j=0;j<k[i];j++){
//             for(int t=s;t>=w[i];t--){
//                 dp[t] = max(dp[t], dp[t-w[i]] + v[i]); 
//             }
//         }
//     }

//     cout<<dp[s];
// }

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, s, v, w, num;
    cin>>s>>n;
    map<int, vector<pair<int,int>>> by_weight;
    for(int i=0;i<n;i++){
        cin>>v>>w>>num;
        by_weight[w].push_back({v, num});
    }
    vector<vector<long long>> dp(by_weight.size()+1, vector<long long> (s+1, INT_MIN));

    int at = 1;
    dp[0][0] = 0;
    for(auto &[w, item] : by_weight){
        sort(item.begin(), item.end(), greater<pair<int, int>>());
        for(int i=0;i<=s;i++){
            dp[at][i] = dp[at-1][i];
            int ind = 0;
            num = 0;
            int cur_in = 0;
            long long price = 0;
            while(ind < item.size() && w * (num+1) <= i){
                num++; 
                price += item[ind].first;
                if(dp[at-1][i-item[ind].first * num] != INT_MIN) dp[at][i] = max(dp[at][i], dp[at-1][i-w * num] + price);
                cur_in++;    
                if(cur_in == item[ind].second) cur_in = 0, ind++;
            }            
        }
        at++;
    }
    // cout<<dp[by_weight.size()][s];
    // cout<<*max_element(dp.back().begin(), dp.back().end());
    long long ans = INT_MIN;
    for(int i=0;i<by_weight.size();i++){
        for(int j=0;j<dp[i].size();j++){
            ans = max(dp[i][j], ans);
            // cout<<dp[i][j]<<endl;
        }
    }
    cout<<ans;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:52:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |             while(ind < item.size() && w * (num+1) <= i){
      |                   ~~~~^~~~~~~~~~~~~
knapsack.cpp:65:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i=0;i<by_weight.size();i++){
      |                 ~^~~~~~~~~~~~~~~~~
knapsack.cpp:66:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for(int j=0;j<dp[i].size();j++){
      |                     ~^~~~~~~~~~~~~

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