Submission #1248441

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248441		attky	Knapsack (NOI18_knapsack)	C++20	100 / 100	88 ms	34372 KiB

knapsack

#include <bits/stdc++.h>
#define int long long

using namespace std;

struct Item {
    int value, number;

    bool operator< (Item other) {
        return value > other.value; 
    }
};

int maxKilo, nbItems;
vector<Item> items[2010];
int dp[2010][2010], maxPrice[2010];

int returnPrice(int poids, int poidsPanier) {
    int iObjet = dp[poidsPanier][poids]+1;
    int iType = 0;
    if(iType >= items[poids].size()) {
        return -2e16;
    }
    while(iObjet > items[poids][iType].number) {
        iObjet -= items[poids][iType].number;
        iType++;
        if(iType >= items[poids].size()) {
            return -2e16;
        }
    }
    return items[poids][iType].value;
}

signed main() {
    //ios_base::sync_with_stdio(false);
    //cin.tie(0);
    cin >> maxKilo >> nbItems;
    for(int loop = 0; loop < nbItems; ++loop) {
        int val, wei, nb;
        cin >> val >> wei >> nb;
        items[wei].push_back({val, nb});
    }
    for(int loop = 0; loop <= maxKilo; ++loop) {
        sort(items[loop].begin(), items[loop].end());
    }
    for(int loop = 1; loop <= maxKilo; ++loop) {
        int maxi = 0, posMaxi = -1;
        for(int looping = 0; looping < loop; ++looping) {
            int ajout = returnPrice(loop-looping, looping);
            if(ajout + maxPrice[looping] >= maxi) {
                maxi = ajout + maxPrice[looping];
                posMaxi = looping;
            }
        }
        for(int looping = 0; looping <= maxKilo; ++looping) {
            dp[loop][looping] = dp[posMaxi][looping];
        }
        dp[loop][loop-posMaxi]++;
        maxPrice[loop] = maxi;
    }
    int maxi = 0;
    for(int loop = 0; loop <= maxKilo; ++loop) {
        maxi = max(maxi, maxPrice[loop]);
    }
    cout << maxi << '\n';
}

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