Submission #968375

#	Time	Username	Problem	Language	Result	Execution time	Memory
968375		ventusliberum	Knapsack (NOI18_knapsack)	C++17	100 / 100	41 ms	3676 KiB

knapsack

/**
 *    title:  Knapsack
**/
#include <bits/stdc++.h>
using namespace std;

#define si(x) int(x.size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define overload(a, b, c, d, ...) d
#define rep0(n) for (int _ = 0; _ < (n); _++)
#define rep1(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); i++)
#define rrep1(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rrep2(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define rep(...) overload(__VA_ARGS__, rep2, rep1, rep0)(__VA_ARGS__)
#define rrep(...) overload(__VA_ARGS__, rrep2, rrep1)(__VA_ARGS__)
template <class T, class U> inline bool chmax(T &a, U b) { return (a < b ? a = b, 1 : 0); }
template <class T, class U> inline bool chmin(T &a, U b) { return (b < a ? a = b, 1 : 0); }
template <class T> istream &operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; }
template <class T> ostream &operator<<(ostream &os, const vector<T> &v) { rep(i, si(v)) os << (i ? " " : "") << v[i]; return os; }
using ll = long long;
constexpr int inf = 1001001001;
constexpr long long infll = 4004004004004004004LL;

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

  int s, n;
  cin >> s >> n;
  vector<vector<pair<int, int>>> use(s+1);
  rep(n) {
    int v, w, k;
    cin >> v >> w >> k;
    use[w].push_back({v, k});
  }
  rep(i, s+1) {
    sort(rall(use[i]));
  }

  vector<int> dp(s+1);
  rep(t, 1, s+1) {
    int sum = 0;
    for (auto [v, k] : use[t]) {
      rep(k) {
        sum += t;
        if (sum > s) goto END;
        rrep(i, t, s+1) {
          chmax(dp[i], dp[i-t] + v);
        }
      }
    }
END:{}
  }

  cout << dp[s] << '\n';
}

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