Submission #1224819

#TimeUsernameProblemLanguageResultExecution timeMemory
1224819bounce_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<pair<ll, ll>> items; rep (i, 0, n) { ll value, weight, count; cin >> value >> weight >> count; ll j(1); while (j<= count){ ll curr_val = value * j; ll curr_weight = weight * j; if (curr_weight > s) break; items.pb({curr_val, curr_weight}); count -= j; j *= 2; } } vll dp(s+1, 0); for (auto item: items) { vll temp = dp; ll value = item.first, weight = item.second; rep (i, weight, s+1){ temp[i] = max(temp[i], dp[i - weight] + value); } dp = move(temp); } 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...