Submission #1117949

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1117949	2024-11-24 12:37:09	classic	Knapsack (NOI18_knapsack)	C++14	73 / 100	1089 ms	19904 KiB

knapsack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  int limitWeight, numItem;
  std::cin >> limitWeight >> numItem;
  std::vector<std::pair<long long, long long>> items;
  for (int index = 0; index < numItem; index++) {
    int value, weight, amount;
    std::cin >> value >> weight >> amount;
    int power2 = 1;
    while (amount >= power2) {
      amount -= power2;
      items.emplace_back(1ll * weight * power2, 1ll * value * power2);
      power2 *= 2;
    }
    if (amount > 0) {
      items.emplace_back(1ll * weight * amount, 1ll * value * amount);
    }
  }
  std::vector<long long> maxValue(limitWeight + 1);
  for (int index = 0; index < (int)items.size(); index++) {
    for (int weight = limitWeight; weight >= 0; weight--) {
      if (items[index].first <= weight) {
        maxValue[weight] = std::max(maxValue[weight], maxValue[weight - items[index].first] + items[index].second);
      }
    }
  }
  std::cout << maxValue[limitWeight];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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