Submission #1225022

#TimeUsernameProblemLanguageResultExecution timeMemory
1225022bounce_29Knapsack (NOI18_knapsack)C++20
37 / 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<pair<int, int>> items; rep (i, 0, n) { ll value, weight, count; cin >> value >> weight >> count; ll j(1); while (j<= count){ int curr_val = value * j; int curr_weight = weight * j; if (curr_weight > s) break; items.pb({curr_val, curr_weight}); count -= j; j *= 2; } if (count > 0) { int curr_val = value * count; int curr_weight = weight * count; if (curr_weight <= s) { items.pb({curr_val, curr_weight}); } } } vector<int> dp(s+1, 0); for (auto item: items) { int 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...