Submission #1184595

#TimeUsernameProblemLanguageResultExecution timeMemory
1184595WarinchaiKnapsack (NOI18_knapsack)C++20
100 / 100
46 ms3268 KiB
#include<bits/stdc++.h> #define int long long using namespace std; vector<pair<int,int>>ob[2005]; vector<pair<int,int>>rob; int dp[2005]; int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(0); int s,n;cin>>s>>n; for(int i=1;i<=n;i++){ int v,w,k;cin>>v>>w>>k; ob[w].push_back({v,k}); } for(int i=1;i<=2000;i++){ sort(ob[i].begin(),ob[i].end(),greater<pair<int,int>>()); if(ob[i].size()>0){ int mx=2000/i+1; for(auto x:ob[i]){ int val=min(mx,x.second); x.second-=val; mx-=val; for(int j=0;j<val;j++)rob.push_back({x.first,i}); if(mx==0)break; } } } dp[0]=0; for(auto [v,w]:rob){ //cerr<<v<<" "<<w<<"\n"; for(int i=2000;i>=0;i--){ int from=i-w; if((from<0||dp[from]==0)&&from)continue; dp[i]=max(dp[i],dp[from]+v); } } int ans=0; for(int i=0;i<=s;i++)ans=max(ans,dp[i]); cout<<ans; }
#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...