Submission #780214

#	Time	Username	Problem	Language	Result	Execution time	Memory
780214		andecaandeci	Knapsack (NOI18_knapsack)	C++17	0 / 100	84 ms	262144 KiB

knapsack

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

#define int long long

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 <= 0 or rem <= 0) return 0;
  if (dp[i][rem] != -1) return dp[i][rem];
  // cout << i << " " << rem << endl;

  int res1 = 0, res2 = 0;

  res2 = solve(i-1, rem);

  if (rem >= e[i]) {
    // k[i]--;

    // res = max(res, solve(i, rem-e[i])+l[i]);
    res1 = solve(i-1, rem-e[i])+l[i];

    // k[i]++;
  }
  

  dp[i][rem] = max(res1, res2);
  return dp[i][rem];
}

signed 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(n, 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