Submission #1247868

#TimeUsernameProblemLanguageResultExecution timeMemory
1247868deeperxdKnapsack (NOI18_knapsack)C++20
17 / 100
1 ms328 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 998244353 #define SIZE 2001 ll dp[SIZE]{0}; float subprog(int n){ float sum = 0; for(int i =1; i<= n; i++){ sum += 1.0/i; } return sum; } int main(){ int s, n; cin >> s >> n; for(int i = 0 ; i < SIZE; i++) dp[i] = -1; dp[0] = 0; map<int, vector<pair<int, int>>> mp; for(int i =0; i < n; i++){ int v, w, k; cin >> v >> w >> k; mp[w].push_back({v, k}); } vector<tuple<int, int, int>> new_queries; for(auto &it : mp){ auto vec = it.second; sort(vec.begin(), vec.end(), greater<pair<int, int>>()); int sum_k = 0; for(auto [v, k] : vec){ if (sum_k + k >= SIZE){ // the last one // to take should have biggest value such sum_k + to_take < SIZE int to_take = SIZE - sum_k - 1; new_queries.push_back({v, it.first, to_take}); break; } else{ new_queries.push_back({v, it.first, k}); } } } for(int i = 0; i < new_queries.size(); i++){ auto [v, w, k] = new_queries[i]; for(int c = s-w; c >= 0; c--){ if (dp[c] == -1) continue; if (dp[c+w] == -1) dp[c+w] = dp[c] + v; else dp[c+w] = max(dp[c+w], dp[c]+v); } } ll mx = 0; for(int i = 0; i <= s; i++){ if (dp[i] == -1)continue; mx = max(mx, dp[i]); } cout << mx << 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...