Submission #1255163

#TimeUsernameProblemLanguageResultExecution timeMemory
1255163_filya_Knapsack (NOI18_knapsack)C++20
73 / 100
228 ms307064 KiB
#include<bits/stdc++.h> typedef long long ll; using namespace std; // Time complexitty O(nlogn + s^2logs) int main() { // ifstream cin("input.txt"); // ofstream cout("output.txt"); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int s, n; cin >> s >> n; vector<array<int, 3>> items(n); vector<vector<int>> items_by_w(s + 1); for (int i = 0; i < n; i++) { int v, w, k; cin >> v >> w >> k; items[i] = {v, w, k}; } sort(items.begin(), items.end()); reverse(items.begin(), items.end()); vector<int> sz(s + 1, 0); vector<pair<int, int>> n_items(1); n_items.reserve(s * 11); for (auto it : items) { while(sz[it[1]] <= s / it[1] + 1 && it[2]) { sz[it[1]]++; n_items.push_back({it[0], it[1]}); it[2]--; } } for (int w = 0; w <= s; w++) { auto v = items_by_w[w]; for (auto u : v) n_items.push_back({u, w}); } n = n_items.size(); ll dp[n + 1][s + 1]; memset(dp, 0, sizeof dp); for (int i = 1; i <= n; i++) { for (int cs = 0; cs <= s; cs++) { dp[i][cs] = dp[i - 1][cs]; if (cs >= n_items[i].second) dp[i][cs] = max(dp[i][cs], dp[i - 1][cs - n_items[i].second] + n_items[i].first); } } cout << dp[n][s] << '\n'; }
#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...