Submission #488508

#	Time	Username	Problem	Language	Result	Execution time	Memory
488508		KienTran	Knapsack (NOI18_knapsack)	C++14	100 / 100	111 ms	3940 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

const int O = 2e3 + 5;
const int N = 2e5 + 5;
const int inf = 1e9;

int n, s, maxK, f[O], dp[O], cnt[O];
vector <pair <int, int>> val[O];

struct triple{
    int v, w, k;
} a[N];

bool how_sort(triple x, triple y){
    if (x.w != y.w) return x.w < y.w;
    return x.v > y.v;
}

main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); srand(time(0));
    cin >> s >> n;
    /*s = rand() % 2000 + 1;
    n = rand() % 100 + 1;
    //cout << s << " " << n << endl;*/
    for (int i = 1; i <= n; ++ i){
        cin >> a[i].v >> a[i].w >> a[i].k;
        /*a[i].k = rand() % 10 + 1;
        a[i].v = rand() % O + 5;
        a[i].w = rand() % s + 1;
        //cout << a[i].v << " " << a[i].w << " " << a[i].k << endl;*/
        maxK = max(maxK, a[i].k);
    }

    sort(a + 1, a + n + 1, how_sort);

    /// sub 1, 2, 3
    if (n <= 100 && maxK <= 10){
        vector <pair <int, int>> b;
        for (int i = 1; i <= n; ++ i){
            for (int j = 1; j <= a[i].k; ++ j) b.push_back({a[i].v, a[i].w});
        }

        for (auto x : b){
            for (int i = 0; i <= s; ++ i) dp[i] = f[i];
            for (int i = 0; i <= s; ++ i){
                if (i >= x.second){
                    f[i] = max(f[i], dp[i - x.second] + x.first);
                }
            }
        }

        int ans = 0;
        for (int i = 0; i <= s; ++ i) ans = max(ans, f[i]);
        cout << ans;// << " " << endl;
        return 0;
    }

    vector <pair <int, int>> b;
    for (int i = 1; i <= n; ++ i){
        int x = a[i].w;
        if (cnt[x] * a[i].w >= s) continue;

        int add = min(s / x, a[i].k);
        cnt[x] += add;

        for (int j = 1; j <= add; ++ j) b.push_back({a[i].v, x});
    }

    memset(f, 0, sizeof(f));
    for (auto x : b){
        for (int i = 0; i <= s; ++ i) dp[i] = f[i];
        for (int i = 0; i <= s; ++ i){
            if (i >= x.second) f[i] = max(f[i], dp[i - x.second] + x.first);
        }
    }

    int res = 0;
    for (int i = 0; i <= s; ++ i) res = max(res, f[i]);

    cout << res;
}
/***
10 5
12 4 6
9 8 3
16 4 9
10 1 2
13 3 8

***/

Compilation message (stderr)

knapsack.cpp:21:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   21 | main(){
      | ^~~~

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