Submission #1219421

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219421		jonatas57	Knapsack (NOI18_knapsack)	C++20	0 / 100	1 ms	328 KiB

knapsack

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long      ll;
typedef vector<int>    vi;
typedef vector<bool>   vb;
typedef pair<int, int> ii;
 
const int INF = 0x3f3f3f3f;
const ll  INFLL = 0x3f3f3f3f3f3f3f3fll;
 
#define each(x, s)  for (auto& x : s)
#define loop(x)     for (int i = 0;i < x;i++)
#define vloop(v, x) for (int v = 0;v < x;v++)
#define iter(a)     a.begin(), a.end()
#define riter(a)    a.rbegin(), a.rend()
#define endl        "\n"
 
struct maxqueue {
  list<ii> q;
  int t = 0, head = 0;
  int del = 0;

  void push(int x) {
    while (!q.empty() and q.back().first < x - del) q.pop_back();
    q.emplace_back(x - del, t++);
  }
  void pop() {
    head++;
    if (!q.empty() and q.front().second < head) q.pop_front();
  }
  int max() {
    return q.empty() ? 0 : q.front().first + del;
  }
  int size() {
    return t - head;
  }
  void clear() {
    q.clear();
    t = head = del = 0;
  }
};

int main() {
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

  int s, n;
  cin >> s >> n;
  vi vs(n), ws(n), ks(n);
  loop(n) cin >> vs[i] >> ws[i] >> ks[i];
  vector<vi> dp(2, vi(s + 1, 0));
  fill(iter(dp[1]), -1);
  int curr = 1;
  loop(n) {
    maxqueue q;
    for (int k = 0;k < ws[i];k++) {
      q.clear();
      if (!k) {
        q.push(0);
        q.del += vs[i];
      }
      for (int j = k;j <= s;j += ws[i]) {
        q.push(dp[curr ^ 1][j]);
        dp[curr][j] = q.max();
        q.del += vs[i];
        if (q.size() > ks[i]) q.pop();
      }
    }
    curr ^= 1;
  }
  cout << dp[curr ^ 1][s] << endl;
  return 0;
}

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