Submission #1265284

#TimeUsernameProblemLanguageResultExecution timeMemory
1265284uzukishinobuKnapsack (NOI18_knapsack)C++20
73 / 100
1096 ms16244 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int f[5000000]; 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); } } // cout << w.size() << "\n"; for (int i=0;i<w.size();i++){ for (int j=b;j>=w[i];j--){ f[j]=max(f[j],v[i]+f[j-w[i]]); // cout << f[j] << " "; } // cout << "\n"; } 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...