Submission #1184094

#TimeUsernameProblemLanguageResultExecution timeMemory
1184094sigmalordKnapsack (NOI18_knapsack)C++20
73 / 100
1093 ms8264 KiB
#include <bits/stdc++.h> using namespace std; long long n,s,dp[1000005]; int main (){ ios_base::sync_with_stdio(false); cin.tie(NULL); memset(dp,0,sizeof dp); cin >> s >> n; for (int i = 1; i <= n; i++){ long long w,v,a; cin >> v >> w >> a; long long temp = 1; while (a > 0){ long long take = min(temp,a); for (int j = s ; j >= 0; j--){ if (j >= w * take) dp[j] = max(dp[j - w * take] + take * v,dp[j]); } a -= take; temp *= 2; } } cout << dp[s]; }
#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...