Submission #1215867

#TimeUsernameProblemLanguageResultExecution timeMemory
1215867muhammadali_2009Knapsack (NOI18_knapsack)C++20
100 / 100
40 ms2884 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int s, n, v, w, k; vector<pair<int,int>> a[2001]; int dp[2001], ans; int32_t main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cin >> s >> n; for(int i = 0; i < n; i++){ cin >> v >> w >> k; a[w].emplace_back(v, k); } for(int i = 1; i <= s; i++){ auto &g = a[i]; sort(g.begin(), g.end(), greater<>()); int idx = 0; for(int cnt = 0; cnt < s / i; cnt++){ if(idx >= (int)g.size()) break; for(int j = s; j >= i; j--){ dp[j] = max(dp[j], dp[j - i] + g[idx].first); ans = max(ans, dp[j]); } if(--g[idx].second == 0) idx++; } } cout << ans; }
#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...