Submission #998112

#TimeUsernameProblemLanguageResultExecution timeMemory
998112coolboy19521Knapsack (NOI18_knapsack)C++17
100 / 100
56 ms9044 KiB
#pragma GCC optimize("Ofast") #include"bits/stdc++.h" #define int long long using namespace std; const int sz = 2e3 + 6; priority_queue <vector <int>> pq[sz]; int dp[sz]; signed main() { cin.tie(nullptr)->sync_with_stdio(false); int s, n; cin >> s >> n; for (int i = 1; i <= n; i ++) { int v, w, k; cin >> v >> w >> k; pq[w].push({v, k}); } for (int i = 1; i <= s; i ++) { int cn = s / i; while (!pq[i].empty() && cn) { auto j = pq[i].top(); j[1] = min(j[1], cn); pq[i].pop(); cn -= j[1]; for (int k = 0; k < j[1]; k ++) { for (int l = s; i <= l; l --) { dp[l] = max(dp[l], dp[l - i] + j[0]); } } } } int mx = 0; for (int i = 0; i <= s; i ++) { mx = max(mx, dp[i]); } cout << mx << '\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...