Submission #1224892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224892		builder_op	Knapsack (NOI18_knapsack)	C++20	100 / 100	34 ms	2888 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
#define int long long

bool cmp(pair<int,int> &a , pair<int,int> &b)
{
    if(a.first == b.first)
    return a.second > b.second;
    return a.first > b.first;
}

int32_t main()
{
    ios :: sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int s , n ; cin >> s >> n;
    vector<pair<int,int>> best[s+1];
    for(int i = 0 ; i < n ; i++)
    {
        int val , wt , q; cin >> val >> wt >> q;
        best[wt].push_back({val,q});
    }
    vector<int> dp(s + 1);
    vector<int> wt , val;
    for(int i = 1 ; i <= s ; i++)
    {
        sort(best[i].begin(),best[i].end(),cmp);
        int q = 0;
        for(auto x : best[i])
        {
            int y = 1;
            while(1)
            {
                if(q > s)   break;
                if(x.second == 0)  break;
                if(y >= x.second)
                y = x.second;
                wt.push_back(i * y);
                q += i * y;
                val.push_back(x.first * y);
                x.second -= y;
                y *= 2;
            }
            if(q > s)   break;
        }
    }

    for(int j = 0 ; j < val.size() ; j++)
    {
        for(int i = s ; i >= 0 ; i--)
        {
            if(i >= wt[j])
            dp[i] = max(dp[i] , dp[i - wt[j]] + val[j]);
        }
    }

    cout << *max_element(dp.begin(),dp.end());
}

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