제출 #1089551

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

knapsack

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

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

inline void solve(){
    ll S, n;
    cin >> S >> n;
    vector<pair<ll, ll> > items;
    for(ll i = 0; i < n; ++i) {
        ll val, w, cnt;
        cin >> val >> w >> cnt;
        cnt = min(cnt, S);
        while(cnt--) {
            items.push_back({val, w});
        }
    }
    const ll inf = 1e18 + 42;
    vector<ll> dp(S + 1, -inf);
    dp[0] = 0;
    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(0);
    cin.tie(NULL); 
    // signed t; cin >> t; while(t--)
        solve();
}

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