제출 #1089568

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1089568		MercubytheFirst	Knapsack (NOI18_knapsack)	C++17	100 / 100	717 ms	57956 KiB

knapsack

#include "bits/stdc++.h"
using namespace std;
using ll = int64_t;
#define endl '\n'

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 37
#endif

void solve() { 
    ll S, n;
    cin >> S >> n;
    map<pair<ll, ll>, ll> mp;
    vector<array<ll, 3> > v(n); // val, weight, count
    for(ll i = 0; i < n; ++i) {
        cin >> v[i][0] >> v[i][1] >> v[i][2];
        v[i][2] = min(v[i][2], S/v[i][1] + 1);
        mp[{v[i][1], -v[i][0]}] += v[i][2];
    }
    for(auto it = mp.begin(); it != mp.end(); ++it) {
        auto [w, val] = it->first;
        ll cnt = it->second;
        cnt = (it->second) = min(cnt, S);
        if(w > S) {
            break;
        }
        while(cnt >= 3) {
            mp[{2*w, 2*val}] += cnt/3;
            cnt = cnt/3 + cnt%3;
        }
        mp[{w, val}] = cnt;
        it = mp.find({w, val});
        // debug(*it);
    }
    const ll inf = 1e18 + 37;
    vector<ll> dp(S + 1, -inf);
    dp[0] = 0;
    vector<int> item_cnt(S + 1);
    vector<pair<ll, ll> > items(S + 1);
    for(auto p : mp) {
        auto [w, val] = p.first;
        ll cnt = p.second;
        if(w > S) {
            break;
        }
        assert(cnt <3);
        for(ll i = 0; i < cnt; ++i) {
            if(item_cnt[w] < S/w + 1) {
                items.push_back({-val, w});
                item_cnt[w]++;
            }
        }
    }
    for(auto [item_val, item_w] : items) {
        for(int W = S; W >= item_w; --W) {
            dp[W] = max(dp[W], dp[W - item_w] + item_val);
        }
    }
    // debug(items);
    cout << *max_element(dp.begin(), dp.end());
} 

signed main(){
    #ifdef LOCAL
    // freopen("test.in", "r", stdin);
    freopen("err.txt", "w", stderr);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

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