제출 #1265285

#제출 시각아이디문제언어결과실행 시간메모리
1265285uzukishinobuKnapsack (NOI18_knapsack)C++20
73 / 100
1096 ms8336 KiB
#include <bits/stdc++.h> using namespace std; long long f[2005]; vector<int> w; vector<int> v; int a,b; 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; w.push_back(x*pow); v.push_back(y*pow); pow*=2; } if (t>0){ w.push_back(x*t); v.push_back(y*t); } } for (int i=0;i<w.size();i++){ for (int j=b;j>=w[i];j--){ f[j]=max(f[j],1LL*(v[i]+f[j-w[i]])); } } cout << f[b]; 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...