Submission #1192842

#TimeUsernameProblemLanguageResultExecution timeMemory
1192842dprtoKnapsack (NOI18_knapsack)C++20
73 / 100
1096 ms1608 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int MAXN = 1e5 + 5; int s, n, v[MAXN], w[MAXN], k[MAXN], dp[MAXN]; void sub1(){ for(int i = 1; i <= n; ++i){ for(int j = s; j >= w[i]; --j){ dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } } cout << dp[s]; } void sub2(){ for(int i = 1; i <= n; ++i){ for(int j = s; j >= w[i]; --j){ for(int q = 1; q <= k[i] and q * w[i] <= j; ++q){ dp[j] = max(dp[j], dp[j - q * w[i]] + q * v[i]); } } } cout << dp[s]; } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> s >> n; int maxk = 0; for(int i = 1; i <= n; ++i){ cin >> v[i] >> w[i] >> k[i]; maxk = max(maxk, k[i]); } if(maxk == 1) sub1(); else sub2(); 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...