Submission #1041204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041204		Antony2357111317	Knapsack (NOI18_knapsack)	C++11	100 / 100	89 ms	5572 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct item {
  ll weight, worth, cnt;
};
bool comp(item i1, item i2){
  if(i1.weight == i2.weight){
    return (i1.worth > i2.worth);
  }
  return (i1.weight < i2.weight);
}
int main() {
  ll S, N;
  cin >> S >> N;
  vector<item> items;
  for(ll i = 0; i < N; i++){
    ll wei, wor, cnt;
    cin >> wor >> wei >> cnt;
    items.push_back({wei, wor, cnt});
  }
  sort(items.begin(), items.end(), comp);
  vector<item> new_item;
  map<ll,ll> myMap;
  for(item item: items){
    if(myMap[item.weight] * item.weight > S){
      continue;
    }
    myMap[item.weight] += item.cnt;
    new_item.push_back(item);
  }
  swap(new_item, items);
  ll dp[S + 1];
  for(ll j = 0; j<=S; j++){
    dp[j] = 0;
  }
  ll mm = 0;
  for(ll i = 1; i <= items.size(); i++){
    for(ll j = S; j >= 0; j--){
      ll ct = 0;
      while (ct * items[i - 1].weight <= j && ct <= items[i - 1].cnt) {
        dp[j] = max(dp[j], dp[j - ct * items[i - 1].weight] + ct * items[i - 1].worth);
        ct++;
      }
      mm = max(mm, dp[j]);
    }
  }
  cout << mm << endl;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:38:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   for(ll i = 1; i <= items.size(); i++){
      |                 ~~^~~~~~~~~~~~~~~

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