Submission #1225060

#TimeUsernameProblemLanguageResultExecution timeMemory
1225060bounce_29Knapsack (NOI18_knapsack)C++20
17 / 100
1 ms328 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define vll vector<long long> #define pb push_back #define endll "\n" #define vvll vector<vector<long long>> const int MOD = 1e9 + 7; #define rep(i, a , n) for (int i = a; i < (n); i++) #define nrep(i, n , a) for (int i = n-1; i >= (a); i--) void solve() { ll s, n; cin >> s >> n; vector<vector<pair<ll, ll>>> items(s+1); rep (i, 0, n) { ll value, weight, count; cin >> value >> weight >> count; if (weight > s) continue; items[weight].push_back({value, count}); } vector<pair<ll, ll>> all_items; rep (i, 1, s+1){ sort(items[i].begin(), items[i].end(), greater<pair<ll, ll>>()); ll accu_weight = 0; for (auto item: items[i]) { ll y = 1; ll value = item.first, count = item.second; while(1){ accu_weight += i * y; if (accu_weight > s) break; if (count == 0) break; if (y > count) y = count; all_items.pb({y*value, i * y}); count -= y; y*=2; } if (accu_weight > s) break; } } vector<ll> dp(s+1, 0); for (auto item: all_items) { ll value = item.first, weight = item.second; nrep (i, s+1, weight){ dp[i] = max(dp[i], dp[i - weight] + value); } } cout << dp[s] << endll; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); return 0; }
#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...