Submission #576758

#	Time	Username	Problem	Language	Result	Execution time	Memory
576758		kalash04	Knapsack (NOI18_knapsack)	C++17	100 / 100	62 ms	3912 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
ll MOD = 1e9 + 7;

struct item {
  int value;
  int copies;
};

void solve() {
  int s, n;
  cin >> s >> n;
  map<int, vector<item>> item_by_weight;
  for(int i = 0; i < n; i++) {
    int v, w, c;
    cin >> v >> w >> c;
    item_by_weight[w].push_back({v, c});
  }
  vector<int> dp(s + 1, 0);
  for(int i = 1; i <= s; i++) {
    if(item_by_weight.count(i) == 0) continue;
    auto vec = item_by_weight[i];
    sort(vec.begin(), vec.end(), [](item a, item b) {
      return a.value < b.value;
    });
    int times = s / i;
    for(int j = 1; j <= times and vec.size() > 0; j++) {
      for(int k = s; k >= i; k--) {
        dp[k] = max(dp[k], dp[k - i] + vec.back().value);
      }
      vec.back().copies--;
      if(vec.back().copies == 0) vec.pop_back();
    }
  }
  cout << dp[s];
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
  cout.tie(NULL);
	solve();
}

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