Submission #967130

#	Time	Username	Problem	Language	Result	Execution time	Memory
967130		agawron	Knapsack (NOI18_knapsack)	C++14	0 / 100	1 ms	604 KiB

knapsack

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair <int, int>;

#define f first
#define s second
#define vi vector <int>
#define pb push_back

constexpr int MAX_S = 2005;

int ks, n;
vector <pii> products[MAX_S];


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> ks >> n;

    for(int i = 0; i < n; i++){
        int we, val, cop;
        cin >> val >> we >> cop;

        products[we].pb({val, cop});
    }

    vector <pii> best_items;

    best_items.pb({0, 0});


    for(int i = 1; i <= 2000; i++){


            sort(products[i].begin(), products[i].end(), [](const pii& p1, const pii p2){ return p1.f > p2.f; });

            int iter = 0;

//            if(i == 10) cerr << "OK" << '\n';


            vector <pii> curr;

            while((curr.size() + 1) * i <= ks && iter < products[i].size()){
//                 if(i == 10) cerr << "OK" << '\n';



                curr.pb({i, products[i].at(iter).f});
                if(--products[i].at(iter).s == 0) iter++;
            }

            for(auto elem: curr){
                best_items.pb(elem);
            }
    }

//    for(auto elem: best_items){
//        cerr << "best_items " << elem.f << ' ' << elem.s << '\n';
//    }

    int sz = best_items.size();

    int dp[sz + 1];

    for(int j = 0; j <= ks; j++){
        dp[j] = 0;
    }

    for(int i = 1; i < sz; i++){

        for(int j = ks; j >= 0; j--){
            if(j - best_items[i].f >= 0) dp[j] = max(dp[j], dp[j - best_items[i].f] + best_items[i].s);
        }

//        for(int j = 0; j <= ks; j++){
//            dp[i][j] = dp[i - 1][j];
//            if(j >= 1) dp[i][j] = max(dp[i][j], dp[i][j - 1]);
//
//            if(j - best_items[i].f >= 0){
//                dp[i][j] = max(dp[i][j], dp[i - 1][j - best_items[i].f] + best_items[i].s);
//                if(j == 20){
//                     cerr << "\n---\n";
//                     cerr << "OK " << i << ' ' << j << '\n';
//                     cerr << "dp " << dp[i][j] << '\n';
//                     cerr << "dp prev " << dp[i - 1][j] << '\n';
//                     cerr << "best item " << best_items[i].f << ' ' << best_items[i].s << '\n';
//                     cerr << "dp oth " << dp[i - 1][j - best_items[i].f];
//                }
//            }
//            cerr << "---" << '\n';
//            cerr << "i j " << i << ' ' << j << '\n';
//            cerr << "dp i j " << dp[i][j] << '\n';
//            cerr << "dp prev " << dp[i - 1][j] << '\n';
//            cerr << "dp oth " << dp[i - 1][j - best_items[i].f] << '\n';
//            cerr << "best items " << best_items[i].f << ' ' << best_items[i].s << '\n';
        }


//    cerr << "\n---\n";

    ll ans = 0;


    for(int k = 0; k <= ks; k++){
//        cerr << dp[k] << ' ';
        ans = max(ans, 1LL * dp[k]);
    }


//    cerr << "\n---\n";

    cout << ans << '\n';

}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:48:41: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |             while((curr.size() + 1) * i <= ks && iter < products[i].size()){
      |                   ~~~~~~~~~~~~~~~~~~~~~~^~~~~
knapsack.cpp:48:55: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |             while((curr.size() + 1) * i <= ks && iter < products[i].size()){
      |                                                  ~~~~~^~~~~~~~~~~~~~~~~~~~

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