Submission #735895

#	Time	Username	Problem	Language	Result	Execution time	Memory
735895		asdfgrace	Knapsack (NOI18_knapsack)	C++17	29 / 100	1 ms	464 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define DEBUG(x) //x
#define A(x) DEBUG(assert(x))
#define PRINT(x) DEBUG(cerr << x)
#define PV(x) DEBUG(cerr << #x << " = " << x << '\n')
#define PV2(x) DEBUG(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define PAR(x) DEBUG(PRINT(#x << " = { "); for (auto y : x) PRINT(y << ' '); PRINT("}\n");)
#define PAR2(x) DEBUG(PRINT(#x << " = { "); for (auto [y, z] : x) PRINT(y << ',' << z << "  "); PRINT("}\n");)
typedef int64_t i64;
const int INF = 1000000007; //998244353;

struct T3 {
  i64 v;
  i64 w;
  i64 k;
};

struct S {
  int s, n;
  vector<T3> a;

  void run() {
    cin >> s >> n;
    a.resize(n);
    for (int i = 0; i < n; ++i) {
      cin >> a[i].v >> a[i].w >> a[i].k;
    }
    sort(a.begin(), a.end(), [&](T3 &x, T3 &y) {
      if (x.w != y.w) return x.w < y.w;
      if (x.v != y.v) return x.v > y.v;
      return x.k < y.k;
    });
    
    vector<i64> cur(s + 1, -1), prev(s + 1, -1), cnt(s + 1, 0);
    cur[0] = 0; prev[0] = 0;
    for (int i = 0; i < n; ++i) {
      PAR(prev);
      for (int j = 0; j + a[i].w <= s; ++j) {
        if (cur[j] == -1) continue;
        if (make_pair(cur[j + a[i].w], -cnt[j + a[i].w])
         < make_pair(cur[j] + a[i].v, -cnt[j] - 1)
         && cnt[j] < a[i].k) {
           PRINT(' '); PV(j);
           cur[j + a[i].w] = cur[j] + a[i].v;
           cnt[j + a[i].w] = cnt[j] + 1;
         } else if (prev[j] != -1 && cur[j + a[i].w] < prev[j] + a[i].v) {
           PV(j);
           cur[j + a[i].w] = prev[j] + a[i].v;
           cnt[j + a[i].w] = 1;
         }
      }
      PAR(cur);
      PAR(cnt);
      prev = cur;
      fill(cnt.begin(), cnt.end(), 0);
    }
    
    i64 ans = 0;
    for (int i = 0; i <= s; ++i) {
      ans = max(ans, cur[i]);
    }
    cout << ans << '\n';
  }
};

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  auto sol = make_unique<S>();
  sol->run();
}

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