Submission #1268122

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268122		zulmuw	Knapsack (NOI18_knapsack)	C++20	73 / 100	1094 ms	19108 KiB

knapsack

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

#define int long long 

struct Barang {
  int v, w, k;
};

struct Nb {
  int v, w;
};

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

  int s, n; cin >> s >> n;
  vector<Barang> bar(n);

  for (auto &[v, w, k]: bar) {
    cin >> v >> w >> k;
  }
  
  vector<Nb> nv;
  for (auto &[v, w, k]: bar) {
    int i=1;
    while (k > 0) {
      int now = min(i, k);
      
      nv.push_back({v * now, w * now});
      
      k -= now;
      i <<= 1;
    }
  }
  
  vector<int> dp(s + 1);
  dp[0] = 0;

  for (auto &[v, w] : nv) {
    for (int i=s; i>=w; --i) {
      dp[i] = max(dp[i], dp[i-w] + v);
    }
  }
  
  cout << dp[s];
}

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