Submission #1188212

#TimeUsernameProblemLanguageResultExecution timeMemory
1188212abcd1234Knapsack (NOI18_knapsack)C++20
73 / 100
342 ms327680 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; using ll = long long; int main() { int s, n; cin >> s >> n; vector<vector<ll>> store(s + 1, vector<ll>(s + 1, 0)); ll v; int w, k; for(int i = 0; i < n; i++) { cin >> v >> w >> k; int j = min(k, s / w); while(j > 0) { store[w].push_back(v); j--; } } for(int i = 1; i <= s; i++) sort(store[i].rbegin(), store[i].rend()); vector<int> dp(s + 1, 0); for(int i = 1; i <= s; i++) { int l = 0; while(store[i][l] != 0 && l < s / i) { for(int j = s; j >= i; j--) dp[j] = max(dp[j - i] * 1LL + store[i][l], dp[j] * 1LL); l++; } } cout << dp[s] << endl; }
#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...