Submission #1002552

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002552		daviedu	Knapsack (NOI18_knapsack)	C++17	100 / 100	48 ms	3868 KiB

knapsack

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

#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ll long long

struct P{
    ll x, y;
};

void dbg_out() { cerr << endl; }
template <typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }


signed main(){
    fastio;
    int s, n;
    cin >> s >> n;
    vector<tuple<int, int, int>> parr;
    for (int i=0; i<n; i++){
        int v, w, k;
        cin >> v >> w >> k;
        parr.push_back({w, v, k});
    }
    sort(rall(parr));
    vector<int> value;
    vector<int> price;
    int cur=0;
    int cnt=0;
    for (auto [w, v, k]: parr){
        if (w != cur) cur = w, cnt = 0;
        int limit = (s-cnt*w)/w;
        for (int i=0; i<min(limit, k); i++){
            value.push_back(v);
            price.push_back(w);
            cnt++;
        }
    }

    vector<int> dp (s+1);
    n = value.size();

    for (int i=0; i<n; i++){
        for (int j=s; j-price[i]>=0; j--){
            dp[j] = max(dp[j], dp[j-price[i]]+value[i]);
        }
    }

    cout << dp[s] << '\n';
}

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