Submission #1089544

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089544		MercubytheFirst	Knapsack (NOI18_knapsack)	C++17	29 / 100	1 ms	456 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);
        mp[{v[i][0], v[i][1]}] += v[i][2];
    }
    debug(mp);
    for(auto it = mp.begin(); it != mp.end(); ++it) {
        auto [val, w] = it->first;
        ll cnt = it->second;
        if(w > S) {
            break;
        }
        while(cnt >= 3) {
            mp[{2*val, 2*w}] += cnt/3;
            cnt = cnt/3 + cnt%3;
        }
        mp[{val, w}] = cnt;
        it = mp.find({val, w});
    }
    debug(mp);
    const ll inf = 1e18 + 37;
    vector<ll> dp(S + 1, -inf);
    dp[0] = 0;
    vector<pair<ll, ll> > items;
    for(auto p : mp) {
        auto [val, w] = 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});
        }
    }
    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());

} 

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:22:5: note: in expansion of macro 'debug'
   22 |     debug(mp);
      |     ^~~~~
knapsack.cpp:9:20: warning: statement has no effect [-Wunused-value]
    9 | #define debug(...) 37
      |                    ^~
knapsack.cpp:36:5: note: in expansion of macro 'debug'
   36 |     debug(mp);
      |     ^~~~~

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