Submission #1186363

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186363		trunz111	Knapsack (NOI18_knapsack)	C++20	100 / 100	63 ms	34376 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;
#define int long long
int limit, n;
map<int, vector<pair<int,int>>> mp;

void Solve()
{
    // dp[i][j] tong lon nhat tao dc tu i tap weight dau tien voi weight <= j
    vector<vector<int>> dp(mp.size()+5, vector<int>(limit+5, 0));

    int i = 1, ans = 0;
    dp[0][0] = 0;
    for (map<int,vector<pair<int,int>>>::iterator it = mp.begin(); it != mp.end(); it++)
    {
        int w = it->first;
        vector<pair<int,int>> vk = it->second;
        sort(vk.begin(), vk.end(), greater<pair<int,int>>());

        for (int m = 0; m <= limit; m++)
        {
            dp[i][m] = dp[i-1][m];
            int copies = 0;
            int cnt_vk = 0;
            int cur_used = 0;
            int profit = 0;

            while ((copies+1) * w <= m && cnt_vk < vk.size())
            {
                copies++;
                profit += vk[cnt_vk].first;
                dp[i][m] = max(dp[i][m], dp[i-1][m-copies*w] + profit);

                cur_used++;
                if (cur_used == vk[cnt_vk].second){
                    cnt_vk++;
                    cur_used = 0;
                }
            }

            ans = max(ans, dp[i][m]);
        }
        i++;
    }
    cout << ans;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> limit >> n;
    for (int i = 1; i <= n; i++)
    {
        int v, w, k; cin >> v >> w >> k;
        mp[w].push_back({v,k});
    }
    Solve();
    return 0;
}

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