Submission #674588

#	Time	Username	Problem	Language	Result	Execution time	Memory
674588		omikron123	Knapsack (NOI18_knapsack)	C++14	100 / 100	125 ms	51508 KiB

knapsack

// https://oj.uz/problem/view/NOI18_knapsack

#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;

// 0-k背包问题

// n <= 1e5, s <= 2000
int n, s;
struct Item {
    int v, w, k;
};
struct Group {
    int w, k;
    int vsum[2005];     // total value of the most valuable i items of weight w
};
ll dp[100005][2005];    // dp[i][j]: max value achieved with items 1..i and weight j
vector<Item> items;
vector<Group> groups;

// sort by weight then value
bool cmp(Item &a, Item &b) {
    if (a.w == b.w)
        return a.v > b.v;
    return a.w > b.w;
}

int main() {
    scanf("%d %d", &s, &n);
    for (int i = 0; i < n; i++) {
        Item it;
        scanf("%d %d %d", &it.v, &it.w, &it.k);
        items.push_back(it);
    }

    sort(items.begin(), items.end(), cmp);
    // 每个重量w，我们只处理floor(s/w)个最有价值的物品
    for (int i = 0; i < items.size(); ) {
        Group g;
        g.w = items[i].w;
        g.k = s / items[i].w;       // we want this many items of this weight
        g.vsum[0] = 0;
        int j = 1;
        while (i < items.size() && items[i].w == g.w) {
            for (int k = 0; k < items[i].k && j <= g.k; k++, j++) {
                g.vsum[j] = g.vsum[j-1] + items[i].v;    
            }
            i++;
        }
        g.k = j-1;
        groups.push_back(g);
    }

    dp[0][0] = 0;
    for (int i = 1; i <= groups.size(); i++) {
        Group g = groups[i-1];
        for (int j = 0; j <= s; j++)
            for (int k = 0; k <= g.k; k++)
                if (j-g.w*k >= 0)
                    dp[i][j] = max(dp[i][j], dp[i-1][j-g.w*k] + g.vsum[k]);
    }
    ll ans = 0;
    for (int i = 0; i <= s; i++)
        ans = max(ans, dp[groups.size()][i]);
    printf("%lld", ans);

    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 0; i < items.size(); ) {
      |                     ~~^~~~~~~~~~~~~~
knapsack.cpp:49:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         while (i < items.size() && items[i].w == g.w) {
      |                ~~^~~~~~~~~~~~~~
knapsack.cpp:60:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Group>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for (int i = 1; i <= groups.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~
knapsack.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     scanf("%d %d", &s, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~
knapsack.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         scanf("%d %d %d", &it.v, &it.w, &it.k);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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