Submission #1177685

#TimeUsernameProblemLanguageResultExecution timeMemory
1177685vyaductKnapsack (NOI18_knapsack)C++20
100 / 100
73 ms1736 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define all(c) (c).begin(), (c).end() #define sz(c) (int)(c).size() #define vt vector #define pb push_back #define F first #define S second void solve() { int s,n; cin>>s>>n; vt<vt<pair<int,int>>> item(s+1); for (int i=0;i<n;i++){ int v,w,k; cin>>v>>w>>k; k = min(k, (s+w-1)/w); item[w].pb(make_pair(v, k)); } vt<ll> dp(s+1, 0); for (int w=1;w<=s;w++){ sort(all(item[w]), greater<>()); vt<int> values; int cn = (s+w-1)/w; for (auto [v,k]: item[w]){ if (cn-k<0) { for (int i=0;i<cn;i++) values.pb(v); break; } for (int i=0;i<k;i++) values.pb(v); cn-=k; } for (int v: values){ for (int x=s;x>=w;x--){ dp[x] = max(dp[x], dp[x-w]+v); } } } cout << dp[s] << endl; } int main() { int tt=1; //cin>>tt; while(tt--) solve(); 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...