Submission #1256376

#TimeUsernameProblemLanguageResultExecution timeMemory
1256376devikareddiKnapsack (NOI18_knapsack)C++20
37 / 100
1093 ms328 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll weight_limit,n; cin >> weight_limit >> n; vector<tuple<ll,ll,ll>> item(n); for(auto &[a,b,c]: item) cin>> a >> b >> c; vector<ll>dp(weight_limit+1,0); for(ll i=0;i<n;i++){ ll weight=get<1>(item[i]),value=get<0>(item[i]); for(ll j=weight_limit;j>0;j--){ ll count=get<2>(item[i]); while(count>0){ if(weight*count<=j){ dp[j] = max(dp[j-(weight*count)]+(count*value),dp[j]); dp[j] = max(dp[j],dp[j-1]); } count--; } } } cout << dp[weight_limit]<<endl; 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...