Submission #1198209

#TimeUsernameProblemLanguageResultExecution timeMemory
1198209almaharbas4Knapsack (NOI18_knapsack)C++20
73 / 100
102 ms36760 KiB
#include<bits/stdc++.h> #define ll long long using namespace std; int main() { ll n,k; cin>>k>>n; vector<ll> val(n),w(n),cap(n); map<ll,vector<pair<ll,ll>>> mapa; for(int i=0;i<n;i++) { cin>>val[i]>>w[i]>>cap[i]; mapa[w[i]].push_back({val[i],cap[i]}); } vector<vector<ll>> dp(mapa.size()+1,vector<ll>(k+1,INT32_MIN)); dp[0][0]=0; ll at=1; for(auto &[a,v]:mapa) { sort(v.rbegin(),v.rend()); for(int i=0;i<=k;i++) { dp[at][i]=dp[at-1][i]; ll copies=0; ll typeat=0; ll profit=0; ll curused=0; while((copies+1)*a<=i&&typeat<=v.size()) { copies++; profit+=v[typeat].first; if(dp[at-1][i-a*copies]!=INT32_MIN) { dp[at][i]=max(dp[at][i],dp[at-1][i-a*copies]+profit); } curused++; if(curused==v[typeat].second) { curused=0; typeat++; } } } at++; } cout<<*max_element(dp.back().begin(),dp.back().end())<<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...