Submission #1265290

#TimeUsernameProblemLanguageResultExecution timeMemory
1265290uzukishinobuKnapsack (NOI18_knapsack)C++20
100 / 100
97 ms28108 KiB
#include <bits/stdc++.h> using namespace std; long long f[2005]; vector<int> w; vector<int> v; int a,b; vector<int> pos[1000005]; signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> b >> a; for (int i=1;i<=a;i++){ int x,y,t; cin >> y >> x >> t; t=min(b/x,t); int pow=1; while (t>=pow ){ t-=pow; int val=y*pow; int cost=x*pow; pos[cost].push_back(val); pow*=2; } if (t>0){ int val=y*t; int cost=x*t; pos[cost].push_back(val); } } for (int i=1;i<=b;i++){ if (pos[i].size()==0){ continue; } sort(pos[i].rbegin(),pos[i].rend()); } for (int j=1;j<=b;j++){ for (int i=b;i>=1;i--){ int prefix=0; int cur=0; int cur1=0; while (cur1<pos[j].size() && i-cur-j>=0){ cur+=j; prefix+=pos[j][cur1]; f[i]=max(f[i],f[i-cur]+prefix); cur1++; } } } cout << f[b] << "\n"; 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...