Submission #1259721

#TimeUsernameProblemLanguageResultExecution timeMemory
1259721krisnandaaaKnapsack (NOI18_knapsack)C++20
37 / 100
1 ms328 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; const int smax = 2000; ll dp[2][smax+5]; int main (){ ios::sync_with_stdio(0); cin.tie(0); int s,n; cin >> s >> n; int cur = 0, nxt = 1; for(int i=1;i<=n;i++){ ll v,w,k; cin >> v >> w >> k; ll pw = 1; while(k > 0){ ll take = min(pw, k); k -= take; int wt = (int)(w * take); ll val = v * take; for(int cap=0; cap<=s; cap++) dp[nxt][cap] = dp[cur][cap]; for(int cap=wt; cap<=s; cap++){ dp[nxt][cap] = max(dp[nxt][cap], dp[cur][cap-wt] + val); } swap(cur,nxt); pw <<= 1; } } cout << dp[cur][s] << "\n"; }
#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...