Submission #769049

#	Time	Username	Problem	Language	Result	Execution time	Memory
769049		vgoofficial	Knapsack (NOI18_knapsack)	C++14	73 / 100	134 ms	35392 KiB

knapsack

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
using pi = pair<int, int>;
struct item {
    int value, weight, number, number2;

};
int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(0);
    int s,n;
    cin >> s >> n;  
    vector<item> items;
    for(int i = 0; i < n; i++) {
        item it;
        cin >> it.value >> it.weight >> it.number;
        it.number2=it.number;
        items.push_back(it);
    }
    sort(items.begin(), items.end(), [](const item a, const item b) -> bool{
        if(b.weight<a.weight) {
            return false;
        }
        if(b.weight==a.weight) {
            if(b.value>a.value) return false;
            return true;
        }
        return true;
    });
    vector<int> uniqWeights;
    uniqWeights.push_back(0);
    int lastWeight = items[0].weight;
    for(int i = 1; i < n; i++) {
        if(items[i].weight!=lastWeight) {
            lastWeight=items[i].weight;
            uniqWeights.push_back(i);
        }
    }
    ll function[s+1][uniqWeights.size()+1];
    for(int i = 0; i <= s; i++) {
        for(int j = 0; j <= uniqWeights.size(); j++) {
            function[i][j]=0;
        }
    }
    ll maxValue = 0;
    int itemIndex = 0;
    for(int j = 0; j < uniqWeights.size(); j++) {
        for(int i = 0; i <= s; i++) {
            itemIndex=uniqWeights[j];
            ll current = function[i][j];
            function[i][j+1]=max(function[i][j+1], current);
            for(int k = i+items[itemIndex].weight; k <= s; k+=items[itemIndex].weight) {
                current += items[itemIndex].value;
                function[k][j+1] = max(function[k][j+1], current);
                items[itemIndex].number--;
                if(items[itemIndex].number==0) {
                    items[itemIndex].number=items[itemIndex].number2;
                    itemIndex++;
                    if(itemIndex>=items.size()||(uniqWeights.size()>(j+1)&&itemIndex>=uniqWeights[j+1])) {
                        break;
                    }
                }
            }
        }
        for(int i = 1; i <= s; i++) {
            function[i][j+1]=max(function[i][j+1], function[i-1][j+1]);
            maxValue=max(maxValue, function[i][j+1]);
        }
    }
    cout << maxValue << endl;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:44:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for(int j = 0; j <= uniqWeights.size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int j = 0; j < uniqWeights.size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~~~~~~
knapsack.cpp:62:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |                     if(itemIndex>=items.size()||(uniqWeights.size()>(j+1)&&itemIndex>=uniqWeights[j+1])) {
      |                        ~~~~~~~~~^~~~~~~~~~~~~~
knapsack.cpp:62:68: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |                     if(itemIndex>=items.size()||(uniqWeights.size()>(j+1)&&itemIndex>=uniqWeights[j+1])) {
      |                                                  ~~~~~~~~~~~~~~~~~~^~~~~~

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