Submission #1222096

#TimeUsernameProblemLanguageResultExecution timeMemory
1222096eduardmmKnapsack (NOI18_knapsack)C++20
12 / 100
0 ms332 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main(){ cin.tie(0)->sync_with_stdio(0); int n, s; cin >> s >> n; vector<ll> v(n), w(n), k(n); for (int i = 0; i < n; ++i){ cin >> v[i] >> w[i] >> k[i]; } vector<ll> dp(s + 1); for (int i = 0; i < n; ++i){ vector<ll> temp(s + 1); for (int j = 0; j <= s; ++j){ if (j == 0 || dp[j] > 0){ if (j + w[i] <= s && dp[j + w[i]] < dp[j] + v[i] && temp[j] < k[i]){ temp[j + w[i]] += temp[j] + 1; dp[j + w[i]] = dp[j] + v[i]; } } } } ll ans = 0; for (int i = 1; i <= s; ++i) ans = max(ans, dp[i]); cout << ans << '\n'; 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...