Submission #733554

#TimeUsernameProblemLanguageResultExecution timeMemory
733554vgoofficialKnapsack (NOI18_knapsack)C++14
73 / 100
216 ms33472 KiB
#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])) {
      |                                                  ~~~~~~~~~~~~~~~~~~^~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...