Submission #1121232

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121232		barkolorious	Knapsack (NOI18_knapsack)	C++17	73 / 100	219 ms	262144 KiB

knapsack

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

#define int uint32_t

const int N = 1e5 + 1;
const int S = 2e3 + 1;
int dp[N][S];

/*
-- Sample 1 --
Input:
15 5
4 12 1
2 1 1
10 4 1
1 1 1
2 2 1
Output:
15

-- Sample 2 --
Input:
20 3
5000 15 1
100 1 3
50 1 4
Output:
5400
*/

int32_t main () {
  int n, s; cin >> s >> n;
  
  int v[n], w[n], k[n];
  for (int i = 0; i < n; i++) cin >> v[i] >> w[i] >> k[i];

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= s; j++) {
      dp[i][j] = dp[i][j - 1];
      int count = max(min(j / w[i - 1], k[i - 1]), (int) 0);
      for (int ii = 0; ii <= count; ii++) {
        int weight = ii * w[i - 1], value = ii * v[i - 1];
        if (j - weight < 0) break;
        dp[i][j] = max(dp[i][j], dp[i - 1][j - weight] + value);
      }
    }
  }
  cout << dp[n][s] << endl;

  return 0;
}

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