Submission #640319

#	Time	Username	Problem	Language	Result	Execution time	Memory
640319		htphong0909	Knapsack (NOI18_knapsack)	C++17	100 / 100	133 ms	27472 KiB

knapsack

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

int DP[10001][10001] = {0};

map<int, vector<pair<int, int>>> byWeight;

int main() {
    int n, m;
    cin >> m >> n;
    vector <pair<int, int>> arr;
    for (int i = 0; i < n; i++)
    {
        int v, w, num;
        cin >> v >> w >> num;
        byWeight[w].push_back({v, num});
    }
    int t = 1;
    for (auto [w, num] : byWeight)
    {
        sort(num.begin(), num.end(), greater<pair<int, int>>());
        for (int j = m; j >= 0; j--)
        {
            DP[t][j] = DP[t - 1][j];
            int typeAt = 0;
            int copies = 1;
            int sum = 0;
            int cur_used = 1;
            while (copies * w <= j && typeAt < int(num.size()))
            {
                sum += num[typeAt].first;
                DP[t][j] = max(DP[t - 1][j - copies * w] + sum, DP[t][j]);
                copies++;
                cur_used++;
                if (cur_used > num[typeAt].second)
                {
                    cur_used = 1;
                    typeAt++;
                }
            }
        }
        t++;
    }
    int ans = 0;
    for (int i = 1; i < t; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            if (DP[i][j] > ans) ans = DP[i][j];
        }
    }
    cout << ans;
    return 0;
}

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