Submission #1261721

#TimeUsernameProblemLanguageResultExecution timeMemory
1261721mentariosKnapsack (NOI18_knapsack)C++20
73 / 100
1096 ms15940 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define _ ios_base::sync_with_stdio(0); cin.tie(0); #define endl '\n' /*ll dp(int i, int l, int x, int y, vector<ll>& memo, vector<ll>& v){ if(i>=x or l>=v[x]) return 0; if(memo[i] != -1) return memo[i]; ll n_c = 1000000; if(v[i] <= l) n_c = dp(i+1,l,x,y,memo,v); return memo[i] = min(dp(i+1, v[i]+y, x, y, memo,v)+1, n_c); } int main(){ int x,y; cin >> x >> y; vector<ll> v(x); for(int i=0; i<x; i++) cin >> v[i]; vector<ll> memo(x, -1); cout << dp(0,0,x,y,memo,v)<<endl; return 0; } */ struct item{ ll v,w; }; const int maxn = 1e6; item listt[maxn]; int main(){ _ ll n, W; cin >> W >> n; const ll MOD = 1000000007; int index = 0; for(int i=1; i<=n; i++){ ll p,h,k; cin >> h >> p >> k; ll c = 1; while(k>c){ k-=c; listt[++index].w = c*p; listt[index].v = c*h; c*=2; } listt[++index].w = k*p; listt[index].v = k*h; } vector<ll> dp(W+1, 0); for(int i=1; i<=index; i++){ for(int j=W; j>=listt[i].w; j--){ dp[j] = max(dp[j], dp[j-listt[i].w] + listt[i].v); } } cout << dp[W] << endl; }
#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...