제출 #1171716

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1171716		abcsedafaef	Knapsack (NOI18_knapsack)	C++20	12 / 100	13 ms	328 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define fast_io                       \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL)

typedef pair<int, pair<int, int>> item;

void solve()
{
    int x, n;
    cin >> x >> n;
    vector<item> items;

    for (int i = 0; i < n; i++)
    {
        int value, weight, amt;
        cin >> value >> weight >> amt;
        if (weight <= x && amt > 0)
        {
            items.push_back({value, {weight, amt}});
        }
    }

    sort(items.begin(), items.end(), [](const item &a, const item &b)
         {
        if (a.first != b.first) return a.first > b.first;
        return a.second.first < b.second.first; });

    n = items.size();
    if (n == 0)
    {
        cout << 0;
        return;
    }

    if (n == 1)
    {
        int maxCopies = min(items[0].second.second, x / items[0].second.first);
        cout << maxCopies * items[0].first;
        return;
    }
    vector<item> new_item;
    map<int,int> myMap;
    for (item item: items) {
        if (myMap[item.second.first] * item.second.first > x) {
            continue;
        }
        myMap[item.second.first] += item.second.second;
        new_item.push_back(item);
    }
    // swap(new_item, items);
    vector<vector<int>> dp(n + 1, vector<int>(x + 1, 0));
    for (int i = n - 1; i >= 0; i--)
    {
        for (int j = 0; j <= x; j++)
        {
            int skip = dp[i + 1][j];
            dp[i][j] = skip;
            for (int k = 1; k <= new_item[i].second.second; k++)
            {
                if (j - k * new_item[i].second.first >= 0)
                {
                    int pick = k * new_item[i].first + dp[i + 1][j - k * new_item[i].second.first];
                    dp[i][j] = max(dp[i][j], pick);
                }
            }
        }
    }

    cout << dp[0][x];
}

int main()
{
    fast_io;
    solve();
    return 0;
}

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