Submission #1020965

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

knapsack

#include <bits/stdc++.h>
using namespace std;

inline void fastInput(int &num) {
    num = 0;
    char ch = getchar();
    bool neg = false;
    if(ch == '-') {
        ch = getchar();
        while(ch >= '0' && ch <= '9') {
            num = (num << 3) + (num << 1) + (ch - '0');
            ch = getchar();
        }
        if(neg) num = -num;
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int s, n;
    fastInput(s);
    fastInput(n);
    
    vector<pair<int, int>> items;  // {value, weight}
    
    for (int i = 0; i < n; ++i) {
        int v, w, k;

        fastInput(v);
        fastInput(w);
        fastInput(k);
        
        int count = 1;
        while (k > 0) {
            int currentCount = min(count, k);
            items.push_back({currentCount * v, currentCount * w});
            k -= currentCount;
            count <<= 1;
        }
    }
    vector<int> dp(s + 1, 0);
    for (const auto &item : items) {
        int v = item.first, w = item.second;
        for (int j = s; j >= w; --j) {
            dp[j] = max(dp[j], dp[j - w] + v);
        }
    }
    cout << dp[s] << '\n';
    return 0;
}

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