Submission #629366

#	Time	Username	Problem	Language	Result	Execution time	Memory
629366		finn__	Knapsack (NOI18_knapsack)	C++17	12 / 100	1083 ms	4828 KiB

knapsack

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

typedef struct item item;
struct item
{
    unsigned i;
    unsigned w;
    unsigned v;
    unsigned k;
};

bool item_cmp(item a, item b)
{
    if (a.w < b.w)
        return 1;
    else if (b.w < a.w)
        return 0;
    else
    {
        if (a.v < b.v)
            return 1;
        else
            return 0;
    }
}

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

    unsigned s, n;
    cin >> s >> n;

    vector<item> items(n);
    for (size_t i = 0; i < n; i++)
    {
        item &x = items[i];
        cin >> x.v >> x.w >> x.k;
        x.i = i;
    }

    sort(items.begin(), items.end(), item_cmp);

    // Holds the maximum achievable value with weight i.
    vector<unsigned> dp(s + 1, 0);
    vector<map<unsigned, unsigned>> used(s + 1);

    for (size_t i = 1; i < s + 1; i++)
    {
        for (size_t j = 0; j < i; j++)
        {
            item search = {.i = 0, .w = i - j, .v = UINT_MAX, .k = 0};
            auto max_item = --upper_bound(items.begin(), items.end(), search, item_cmp);

            while (max_item != --items.begin() &&
                   used[j].find(max_item->i) != used[j].end() &&
                   used[j][max_item->i] == max_item->k)
                max_item--;

            if (max_item == --items.begin())
            {
                if (dp[j] > dp[i])
                {
                    dp[i] = dp[j];
                    used[i] = used[j];
                }
            }
            else
            {
                if (dp[j] + max_item->v > dp[i])
                {
                    dp[i] = dp[j] + max_item->v;
                    used[i] = used[j];
                    if (used[i].find(max_item->i) == used[i].end())
                        used[i][max_item->i] = 1;
                    else
                        used[i][max_item->i]++;
                }
            }
        }
    }

    cout << dp[s] << '\n';
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:54:43: warning: narrowing conversion of '(i - j)' from 'size_t' {aka 'long unsigned int'} to 'unsigned int' [-Wnarrowing]
   54 |             item search = {.i = 0, .w = i - j, .v = UINT_MAX, .k = 0};
      |                                         ~~^~~

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