Submission #1224873

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224873		builder_op	Knapsack (NOI18_knapsack)	C++20	73 / 100	1097 ms	18548 KiB

knapsack

#include <bits/stdc++.h>
using namespace std; 
#define ll long long
#define vll vector<long long>
#define pb push_back
#define endll "\n"
#define vvll vector<vector<long long>>
const int MOD = 1e9 + 7;
#define rep(i, a , n) for (int i = a; i < (n); i++)
#define nrep(i, n , a) for (int i = n-1; i >= (a); i--)

void dbg_out() { cerr << endl; }

template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }

template<typename K, typename V>
void dbg_out(const map<K, V>& m) {
    cerr << "{ ";
    for (const auto& pair : m) {
        cerr << "(" << pair.first << ", " << pair.second << ") ";
    }
    cerr << "}";
}

template<typename T>
void dbg_out(const set<T>& s) {
    cerr << "{ ";
    for (const auto& elem : s) {
        cerr << elem << " ";
    }
    cerr << "}";
}

template<typename T>
void dbg_out(const vector<T>& v) {
    cerr << "[ ";
    for (const auto& elem : v) {
        cerr << elem << " ";
    }
    cerr << "]";
}

#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)

void solve()
{
    ll s , n ; cin >> s >> n;
    vll prize(n) , weight(n) , qty(n);

    for(int i = 0 ; i < n ; i++)
    {
        cin >> prize[i] >> weight[i] >> qty[i];
        qty[i] = min(qty[i] , s/weight[i]);
    }

    vll dp(s+1);
    vll weightt , prizz;
    dp[s] = 0;
    rep(idx, 0, n) 
    {
        ll v = prize[idx], w = weight[idx], k = min(qty[idx], s / w);
        for (ll p = 1; k > 0; p <<= 1) 
        {
            ll take = min(p, k);     
            weightt.pb(take * w);
            prizz.pb(take * v);
            k -= take;
        }
    }


    for(ll j = 0 ; j < weightt.size() ; j++)
    {
        for(ll i = s ; i >= 0 ; i--)
        {
            if(i >= weightt[j])
            dp[i] = max(dp[i - weightt[j]] + prizz[j], dp[i]);
        }
    }

    cout << dp[s];
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    auto start = chrono::high_resolution_clock::now();
    int tt = 1; //cin >> tt;
    while(tt--)
        solve();
    auto end = chrono::high_resolution_clock::now();
    chrono::duration<double> duration = end - start;
    //cout << "Time taken: " << duration.count() << " seconds" << endl;
    
    return 0;
}

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