Submission #951800

#	Time	Username	Problem	Language	Result	Execution time	Memory
951800		TrendBattles	Knapsack (NOI18_knapsack)	C++14	100 / 100	101 ms	5864 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;
using lli = int64_t;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int W, N; cin >> W >> N;
    
    vector <vector <int>> store(W + 1);
    for (int i = 1; i <= N; ++i) {
        int value, weight, cnt; cin >> value >> weight >> cnt;
        
        lli k = 1;
        while (cnt >= k) {
            if (weight * k <= W) {
                store[weight * k].push_back(value * k);
            }
            
            cnt -= k;
            k <<= 1;
        }
        
        if (cnt and (lli) weight * cnt <= W) {
        	store[weight * cnt].push_back(value * cnt);
        }
    }
    
    vector <lli> dp(W + 1);
    for (int i = 1; i <= W; ++i) {
    	sort(store[i].begin(), store[i].end(), greater <int> ());
    	if (store[i].size() > W / i) {
    		store[i].erase(store[i].begin() + W / i, store[i].end());
    	}
    	
    	for (int v : store[i]) {
    		for (int cur_w = W; cur_w >= i; --cur_w) {
    			dp[cur_w] = max(dp[cur_w], dp[cur_w - i] + v);
    		}
    	}
    }
    cout << dp[W];
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:33:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |      if (store[i].size() > W / i) {
      |          ~~~~~~~~~~~~~~~~^~~~~~~

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