Submission #1227683

#TimeUsernameProblemLanguageResultExecution timeMemory
1227683thesenKnapsack (NOI18_knapsack)C++20
49 / 100
3 ms1864 KiB
#include <bits/stdc++.h> #define pb push_back #define ll long long #define vint vector <int> #define vll vector <ll> #define vbool vector<bool> #define pairint pair<int,int> #define pairll pair<ll,ll> #define fi first #define sc second #define rever greater<ll>() using namespace std; struct dta{ ll v, w, k; }; void solve(ll tc){ ll s, n; cin >> s >> n; vector<vector<pairll>> a(2001); ll v, w, k; while(n--){ cin >> v >> w >> k; a[w].pb({v, k}); } for(int i = 1; i <= 2000; i++){ sort(a[i].begin(), a[i].end(), greater<pairll>()); } vector<dta> c(1); ll tot; for(int i = 1; i <= 2000; i++){ tot = 0; for(pairll x : a[i]){ if(tot >= s){ break; } c.pb({x.fi, i, x.sc}); tot += i*k; } } vector<vll> dp(c.size(), vll(s+1, 0)); for(int i = 1; i < c.size(); i++){ for(int j = 1; j <= s; j++){ dp[i][j] = max(dp[i-1][j], dp[i][j-1]); for(ll k = 1; k <= c[i].k; k++){ if(j-c[i].w*k < 0){ break; } dp[i][j] = max(dp[i][j], dp[i-1][j-c[i].w*k] + c[i].v*k); } } }cout << dp[c.size()-1][s] << endl; } int main(){ ll t; t = 1; for(int i = 1; i <= t; i++){ solve(i); } }
#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...