Submission #780159

#	Time	Username	Problem	Language	Result	Execution time	Memory
780159		devariaota	Knapsack (NOI18_knapsack)	C++17	0 / 100	87 ms	262144 KiB

knapsack

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

int l[100005], e[100005], k[100005], dp[100005][2005];
// l = val, e = cost, k = count
int t, n;

int solve(int i, int rem) {
  if (i > n or rem <= 0) return 0;
  if (dp[i][rem] != -1) return dp[i][rem];
  // cout << i << " " << rem << endl;

  int res = INT_MIN;

  if (rem >= e[i]) {
    k[i]--;
    if (k[i] > 0) {
      res = max(res, solve(i, rem-e[i])+l[i]);
    }
    res = max(res, solve(i+1, rem-e[i])+l[i]);
    k[i]++;
  }
  res = max(res, solve(i+1, rem));

  return dp[i][rem] = res;
}

int main() {
  cin >> t >> n;
  for (int i = 1; i <= n; i++) {
    cin >> l[i] >> e[i] >> k[i];
  }
  memset(dp, -1, sizeof(dp));
  cout << solve(1, t) << endl;
  // for (int i = 1; i <= n; i++) {
  //   for (int j = 0; j <= t; j++) {
  //     cout << dp[i][j] << "	";
  //   }
  //   cout << endl;
  // }
}

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