Submission #918879

#	Time	Username	Problem	Language	Result	Execution time	Memory
918879		imann	Knapsack (NOI18_knapsack)	C++17	29 / 100	3 ms	4952 KiB

knapsack

#include <iostream>

typedef long long ll;

const int MAX_N = 1000*100 + 10;
const int MAX_S = 2*1000 + 10;
ll Vs[MAX_N];
ll Ws[MAX_N];
ll Ks[MAX_N];
std::pair<int, int> dp[MAX_N][MAX_S];

int solve(int s, int n) {
  for (int i = 0; i <= s; ++i) {
    int c = std::min(Ks[0], i / Ws[0]);
    dp[0][i] = {c * Vs[0], i - c * Ws[0]};
  }
  
  for (int i = 1; i < n; ++i) {
    for (int j = 0; j <= s; ++j) {
      int c = std::min(Ks[i], j / Ws[i]);
      int v = c * Vs[i];
      int c2 = std::min(Ks[i], dp[i - 1][j].second / Ws[i]);
      int v2 = c2 * Vs[i];
      if (dp[i - 1][j].first + v2 >= dp[i - 1][j - c * Ws[i]].first + v) {
        dp[i][j] = {dp[i - 1][j].first + v2, dp[i - 1][j].second - c2 * Ws[i]};
      } else {
        dp[i][j] = {dp[i - 1][j - c * Ws[i]].first + v, dp[i - 1][j - c * Ws[i]].second};
      }
    }
  }
  
  return dp[n - 1][s].first;
}

int main() {
  int s, n; std::cin >> s >> n;
  for (int i = 0; i < n; ++i)
    std::cin >> Vs[i] >> Ws[i] >> Ks[i];
  std::cout << solve(s, n) << std::endl;
}

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