Submission #1201912

#TimeUsernameProblemLanguageResultExecution timeMemory
1201912prideliqueeeKnapsack (NOI18_knapsack)C++20
100 / 100
40 ms1864 KiB
#include<bits/stdc++.h> using namespace std; #define f first #define s second int main() { ios_base::sync_with_stdio(0); cin.tie(0); int s,n; cin>>s>>n; priority_queue<pair<int,int>> pq[s+1]; for(int i=0;i<n;i++) { int v,w,s; cin>>v>>w>>s; pq[w].push({v,s}); } vector<pair<int,int>> a; for(int i=1;i<=s;i++) { int cnt=(s+i-1)/i; while(!pq[i].empty()&&cnt) { int v=pq[i].top().f,s=pq[i].top().s; pq[i].pop(); int temp=s; while(cnt>=0&&temp>0) { a.push_back({v,i}); temp--; cnt--; } } } int dp[s+1]; memset(dp,0,sizeof dp); int ans=0; for(auto x:a) { int v=x.f,w=x.s; for(int i=s;i>=w;i--) { dp[i]=max(dp[i],dp[i-w]+v); 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...