Submission #1089565

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089565		MercubytheFirst	Knapsack (NOI18_knapsack)	C++17	73 / 100	1057 ms	89524 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<pair<ll, ll> > items;
    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) {
            items.push_back({val, w});
        }
    }
    debug(items);
    assert(items.size() <= 1600000u);
    for(auto [item_val, item_w] : items) {
        for(ll W = S; W >= item_w; --W) {
            dp[W] = max(dp[W], dp[W - item_w] + item_val);
        }
    }
    cout << *max_element(dp.begin(), dp.end()) << '\n';

} 

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();
}

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:9:20: warning: statement has no effect [-Wunused-value]
    9 | #define debug(...) 37
      |                    ^~
knapsack.cpp:35:9: note: in expansion of macro 'debug'
   35 |         debug(*it);
      |         ^~~~~
knapsack.cpp:9:20: warning: statement has no effect [-Wunused-value]
    9 | #define debug(...) 37
      |                    ^~
knapsack.cpp:52:5: note: in expansion of macro 'debug'
   52 |     debug(items);
      |     ^~~~~

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