제출 #1036804

#제출 시각아이디문제언어결과실행 시간메모리
1036804ocasuKnapsack (NOI18_knapsack)C++17
73 / 100
1008 ms1308 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int inf=1e12; signed main(){ int S,n; cin>>S>>n; vector<multiset<int>> items(S+1); for (int i=0; i<n; i++){ int v,w,k; cin>>v>>w>>k; k=min(k, S/w+1); while(k--) items[w].insert(v); while((int)(items[w].size()) > S/w+1) { items[w].erase(items[w].begin()); } } vector<int> dp(S+1,-inf); //current maximum value of a subset with total weight w dp[0]=0; for (int w=0; w<=S; w++){ for (auto v: items[w]){ for (int i=S; i>=w; i--){ dp[i]=max(dp[i], dp[i-w]+v); } } } int ans=0; for (auto i: dp) ans=max(ans, i); cout<<ans<<'\n'; }
#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...