oj.uz

Submission #966979

# Submission time Handle Problem Language Result Execution time Memory
966979 2024-04-20T19:24:44 Z agawron Knapsack (NOI18_knapsack) C++14
12 / 100
 1 ms 856 KB 
#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() <= ks/i && 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][ks];

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

    for(int i = 1; i < sz; i++){
        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";
//
//    for(int i = 1; i < sz; i++){
//        for(int j = 0; j <= ks; j++){
//            cerr << dp[i][j] << ' ';
//        }
//
//        cerr << "\n";
//    }
//
//    cerr << "\n---\n";




    cout << dp[sz - 1][ks] << '\n';

}

Compilation message

knapsack.cpp: In function 'int main()':
knapsack.cpp:48:31: 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() <= ks/i && iter < products[i].size()){
      |                   ~~~~~~~~~~~~^~~~~~~
knapsack.cpp:48: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]
   48 |             while(curr.size() <= ks/i && iter < products[i].size()){
      |                                          ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 856 KB Output is correct
4 Correct 0 ms 344 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 856 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Incorrect 0 ms 504 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 856 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Incorrect 0 ms 504 KB Output isn't correct
6 Halted 0 ms 0 KB -