Submission #1217334

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217334		jonatas57	Knapsack (NOI18_knapsack)	C++20	12 / 100	3 ms	584 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() {
    head = t = del = 0;
    q.clear();
  }
};

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);
  vector<maxqueue> qs(2000);
  int curr = 1;
  loop(n) {
    loop(ws[i]) qs[i].clear();
    dp[curr][0] = 0;
    qs[0].push(0);
    qs[0].del += vs[i];
    for (int j = 1, k = 1 % ws[i];j <= s;j++, k = k + 1 == ws[i] ? 0 : k + 1) {
      qs[k].push(dp[curr ^ 1][j]);
      dp[curr][j] = qs[k].max();
      qs[k].del += vs[i];
      if (qs[k].size() > ks[i]) qs[k].pop();
    }
    curr ^= 1;
  }
  cout << dp[curr ^ 1][s] << endl;
  return 0;
}

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