제출 #1317933

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1317933		Aratab	Knapsack (NOI18_knapsack)	C++20	0 / 100	1 ms	332 KiB

knapsack

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

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, int> pli;

// const
const ll LINF = (ll)(1e18) + 5;
const int INF = (int)(1e9) + 5;


// loop
#define FOR(i, l, r) for (int i=l; i<r; i++)
#define F0R(i, n) for (int i=0; i<n; i++)


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


  int S, N;
  cin >> S >> N;
  vector<vector<pli>> W(S+1);
  for (int i=0; i<N; i++) {
    int v, w, k;
    cin >> v >> w >> k;
    W[w].push_back({v, k});
  }
  for (int i=1; i<=S; i++) {
    if (W[i].size() > 0) {
      sort(W[i].rbegin(), W[i].rend());
    }
  }

  vector<ll> dp(S+1, -LINF);
  dp[0] = 0;
  for (int w = 1; w <= S; w++) {
    if (W[w].size() == 0) continue;

    int maxt = S / w;
    int cnt = 0;
    for (auto &[v, k] : W[w]) {
      for (int i = 0; i < k && cnt < maxt; i++) {
        for (int x=S; x>=0; x--) {
          if (dp[x] > -LINF && x + w <= S) {
            dp[x + w] = max(dp[x + w], dp[x] + v);
            cnt++;
          }
        }
      }
      if (cnt >= maxt) {
        break;
      }
    }
  }

  ll ans = 0;
  for (int i=0; i<=S; i++) {
    ans = max(ans, dp[i]);
  }
  cout << ans << '\n';
}

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