Submission #654552

#	Time	Username	Problem	Language	Result	Execution time	Memory
654552		pauloamed	Knapsack (NOI18_knapsack)	C++14	100 / 100	128 ms	5324 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int MAXN = 2010;

vector<pair<int,int>> W0[MAXN];
vector<pair<int,int>> v;

int K[MAXN];

int32_t main(){
  int S, n; cin >> S >> n;
  for(int i = 0; i < n; ++i){
    int v, w, k; cin >> v >> w >> k;
    W0[w].push_back({v, k});
  }

  for(int w = 1; w <= S; ++w){
    vector<int> tmp;
    sort(W0[w].rbegin(), W0[w].rend());

    for(auto &[x, k] : W0[w]){
      while(tmp.size() <= ((S+w-1)/w) && k--){
        tmp.push_back(x);
      }
    }

    for(auto x : tmp) v.push_back({x, w});
  }

  // cout << v.size() << "\n";

  int ans = 0;
  for(auto [x, w] : v){
    for(int i = S - w; i >= 0; --i){
      K[i + w] = max(K[i + w], K[i] + x);
      ans = max(ans, K[i + w]);
    }
  }
  cout << ans << "\n";

}

Compilation message (stderr)

knapsack.cpp: In function 'int32_t main()':
knapsack.cpp:23:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |     for(auto &[x, k] : W0[w]){
      |               ^
knapsack.cpp:24:24: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   24 |       while(tmp.size() <= ((S+w-1)/w) && k--){
      |             ~~~~~~~~~~~^~~~~~~~~~~~~~
knapsack.cpp:35:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |   for(auto [x, w] : v){
      |            ^

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