Submission #1256384

#TimeUsernameProblemLanguageResultExecution timeMemory
1256384devikareddiKnapsack (NOI18_knapsack)C++20
37 / 100
1097 ms66136 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); vector<pair<ll,ll>> expanded; for(auto &[a,b,c]: item) cin>> a >> b >> c; for( auto [a,b,c]:item){ for( ll i=0;i<c;i++){ expanded.push_back({a,b}); } } vector<ll>dp(weight_limit+1,0); for(ll i=0;i<expanded.size();i++){ ll weight=(expanded[i].second),value=(expanded[i].first); for(ll j=weight_limit;j>0;j--){ if(j>=weight)dp[j] = max(dp[j-(weight)]+value,dp[j]); dp[j] = max(dp[j],dp[j-1]); } } 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...