제출 #847309

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
847309		vjudge1	Knapsack (NOI18_knapsack)	C++14	100 / 100	32 ms	3416 KiB

knapsack

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

#define int long long
#define isz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

using ld = long double;
const int inf = 2e18;
const ld eps = 1e-9;

const int N = 1e5 + 5;
const int S = 2e3 + 1;

int n, s;
vector<pair<int, int>> items[S];
int dp[S];

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

  cin >> s >> n;
  for (int i = 1; i <= n; ++i) {
    int v, w, k; cin >> v >> w >> k;
    items[w].emplace_back(v, k);
  }
  vector<array<int, 3>> a;
  for (int i = 1; i <= s; ++i) {
    sort(all(items[i]), greater<>());
    int bound = s / i;
    for (pair<int, int> it: items[i]) {
      int v, k; tie(v, k) = it;
      int taken = min(bound, k);
      a.push_back({i, v, taken});
      bound -= taken;
      if (bound == 0) {
        break;
      }
    }
  }
  vector<pair<int, int>> b;
  for (int i = 0; i < isz(a); ++i) {
    int w = a[i][0], v = a[i][1], k = a[i][2];
    int pw2 = 1;
    while (pw2 <= k) {
      b.emplace_back(w * pw2, v * pw2);
      k -= pw2;
      pw2 *= 2;
    }
    if (k > 0) {
      b.emplace_back(w * k, v * k);
    }
  }
  for (pair<int, int> it: b) {
    int w, v; tie(w, v) = it;

    for (int i = s; i >= w; --i) {
      dp[i] = max(dp[i], dp[i - w] + v);
    }
  }
  int ans = -inf;
  for (int i = 0; i <= s; ++i) {
    ans = max(ans, dp[i]);
  }
  cout << ans;
}

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