Submission #780223

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

knapsack

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

int t, n, val[100005], cost[100005], remain[100005], dp[100005][2005];

int solve(int i, int rem) {
  if (i < 0 or rem <= 0) return 0;
  if (dp[i][rem] != -1) return dp[i][rem];

  int res1, res2=0;

  res1 = solve(i-1, rem);

  if (rem >= cost[i]) {
    res2 = solve(i-1, rem-cost[i])+val[i];
  }

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

int main() {
  cin >> t >> n;
  for (int i = 0; i < n; i++) cin >> val[i] >> cost[i] >> remain[i];

  memset(dp, -1, sizeof(dp));
  cout << solve(n-1, t) << endl;
}

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