Submission #1209826

#TimeUsernameProblemLanguageResultExecution timeMemory
1209826borekkingKnapsack (NOI18_knapsack)C++20
73 / 100
417 ms327680 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int s, n; cin >> s >> n; vector<vector<int>> items(s+1); for (int i = 0; i < n; i++) { int v, w, k; cin >> v >> w >> k; int amount = min(s/w + 1, k); for (int j = 0; j < amount; j++) { items[w].push_back(v); } } vector<ll> weight(1), profit(1); for (int i = 1; i <= s; i++) { sort(items[i].begin(), items[i].end()); reverse(items[i].begin(), items[i].end()); int amount = min((int) items[i].size(), s/i+1); for (int j = 0; j < amount; j++) { weight.push_back(i); profit.push_back(items[i][j]); } } n = weight.size(); vector<vector<ll>> dp(s+1, vector<ll>(n, 0)); for (ll w = 1; w <= s; w++) { for (int i = 1; i < n; i++) { dp[w][i] = dp[w][i-1]; if (w-weight[i] >= 0) { dp[w][i] = max(dp[w][i], profit[i] + dp[w-weight[i]][i-1]); } } } cout << dp[s][n-1] << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...