제출 #528321

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
528321		theysoldtheworld	Knapsack (NOI18_knapsack)	C++14	37 / 100	43 ms	1996 KiB

knapsack

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

struct Item {
  long long v , w , k;
};
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int S , N;
  cin >> S >> N;
  vector<Item> a(N);
  for (int i = 0 ; i < N ; i++) {
    cin >> a[i].v >> a[i].w >> a[i].k;
    a[i].k = min(a[i].k , S * 1LL);
  }
  const long long inf = (long long)1e18;
  auto Get_candidates = [&](int val) {
    vector<long long> c;
    for (int i = 30 ; i >= 0 ; i--) {
      long long cur = (1LL << i);
      if (cur <= val) {
        c.push_back(cur);
        c.push_back(val - (cur - 1));
        c.push_back(val - cur);
      }
    }
    return c;
  };

  vector<vector<long long>> dp(N , vector<long long> (S + 1 , -1));
  function<long long(int , long long)> Solve = [&](int id , long long cur) {
    if (cur < 0) return -inf;
    if (id == N) return 0LL;
    auto &p = dp[id][cur];
    if (p != -1) return p;
    long long ans = -inf;
    vector<long long> c = Get_candidates(a[id].k);
    for (int i = 0 ; i < (int)c.size() ; i++) {
      assert(c[i] <= a[id].k);
      long long cost = a[id].w * c[i];
      long long add = a[id].v * c[i];      
      ans = max(ans , Solve(id + 1 , cur - cost) + add);
    }
    ans = max(ans , Solve(id + 1 , cur));
    return p = ans;
  };
  cout << Solve(0 , S) << '\n';
  return 0; 
}

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