Submission #733554

#	Time	Username	Problem	Language	Result	Execution time	Memory
733554		vgoofficial	Knapsack (NOI18_knapsack)	C++14	73 / 100	216 ms	33472 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;
    bool operator<(item other) {
        if(other.weight<weight) {
            return false;
        }
        if(other.weight==weight) {
            if(other.value>value) {
                return false;
            }
            return true;
        }
        return true;
    }
};
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(begin(items), end(items));
    //for(item i: items) cout << "value: " << i.value << " weight: " << i.weight << " number: " << i.number << endl;
    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);
        }
    }
    //for(int i: uniqWeights) cout << i << endl;
    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 i = items[0].weight; i <= s; i+=items[0].weight) {
        function[i][1]=function[i-items[0].weight][1]+items[itemIndex].value;
        items[itemIndex].number--;
        if(items[itemIndex].number==0) {
            itemIndex++;
            if(itemIndex>=items.size()||(uniqWeights.size()>1&&itemIndex>=uniqWeights[1])) {
                //cout << "got here " << itemIndex << endl;
                break;
            }
        }
    }
    */
    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])) {
                        //cout << "got here " << itemIndex << " " << j << endl;
                        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:48:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for(int j = 0; j <= uniqWeights.size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(int j = 0; j < uniqWeights.size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~~~~~~
knapsack.cpp:79:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |                     if(itemIndex>=items.size()||(uniqWeights.size()>(j+1)&&itemIndex>=uniqWeights[j+1])) {
      |                        ~~~~~~~~~^~~~~~~~~~~~~~
knapsack.cpp:79:68: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   79 |                     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