Submission #1224811

#TimeUsernameProblemLanguageResultExecution timeMemory
1224811bounce_29Knapsack (NOI18_knapsack)C++20
0 / 100
199 ms7748 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; vvll items(n, vll(3)); rep (i, 0, n) { cin >> items[i][0] >> items[i][1] >> items[i][2]; } vll dp(s+1, 0); for (auto item: items) { vll temp = dp; ll weight = item[0], value = item[1], count = item[2]; rep (i, weight, s+1){ rep (j, 1, count+1){ if (i - j * weight >= 0) { temp[i] = max(temp[i], dp[i - j * weight] + j * value); } else { break; } } } dp = move(temp); } cout << dp[s] << endll; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int tt = 1; cin >> tt; while(tt--) 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...