Submission #1097811

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097811		ljlkj	Knapsack (NOI18_knapsack)	C++14	73 / 100	169 ms	262144 KiB

knapsack

#include<iostream>

#include<vector>
#include<algorithm>
#include<map>
#include<set>

using namespace std;
int main(){
    long long s , n;
    cin >> s >> n;
    vector<vector<vector<long long>>> products(s + 1);
    for(long long i = 0; i < n; i++){
        long long v , w , k;
        cin >> v >> w >> k;
        products[w].push_back({v , k , w});
    }


    vector<vector<long long>> finalProduct;
    for(long long i = 1; i <= s; i++){
        sort(products[i].begin() , products[i].end());
        long long sum = 0;
        for(long long j = products[i].size() - 1; j >= 0; j--){
            if(sum + products[i][j][2] * products[i][j][1] > s){
                 long long remain = s - sum;
                 finalProduct.push_back({products[i][j][0] , min(remain / products[i][j][2] , products[i][j][1]) , products[i][j][2]});
                 if(remain % (products[i][j][2]) != 0){
                      if(finalProduct.back()[1] < products[i][j][1]) finalProduct.back()[1]++;
                 }
            }
            else {
                sum += products[i][j][2] * products[i][j][1];
                finalProduct.push_back({products[i][j][0] , products[i][j][1] , products[i][j][2]});
            }
        }
    }
    // long long prCount = 0;
    // for(long long i=  0; i < finalProduct)
    // vector<vector<long long>> 

    // cout << "test: " << endl;
    // for(long long i = 0; i < finalProduct.size(); i++){
    //     cout << finalProduct[i][0] << ' ' << finalProduct[i][2] << ' ' << finalProduct[i][1] << endl;
    // }
    // cout << "end Test" << endl;


    vector<vector<long long>> dp(finalProduct.size() + 1);
    for(long long i = 0; i < finalProduct.size() + 1; i++) dp[i].resize(s + 1);
    for(long long i = 0; i < s + 1; i++) dp[0][i] = 0;
    for(long long i = 0; i < finalProduct.size() + 1; i++){
        dp[i][0] = 0;
    }
    for(long long i = 1; i < finalProduct.size() + 1; i++){
        for(long long j = 1; j < s + 1; j++){
            dp[i][j] = dp[i - 1][j];
            for(long long u = 1; u <= finalProduct[i - 1][1]; u++){
              if(j - (u * finalProduct[i - 1][2]) >= 0) dp[i][j] = max(dp[i][j] , dp[i - 1][j - (u * finalProduct[i - 1][2])] + u * finalProduct[i - 1][0]);
              else break;
            }
        }
    }

    long long ans = 0;
    for(long long i = 0; i < s + 1; i++){
        ans = max(ans , dp[finalProduct.size()][i]);
    }
    cout << ans << endl;



    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:50:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(long long i = 0; i < finalProduct.size() + 1; i++) dp[i].resize(s + 1);
      |                          ~~^~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:52:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(long long i = 0; i < finalProduct.size() + 1; i++){
      |                          ~~^~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:55:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(long long i = 1; i < finalProduct.size() + 1; i++){
      |                          ~~^~~~~~~~~~~~~~~~~~~~~~~~~

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