Submission #1195935

#TimeUsernameProblemLanguageResultExecution timeMemory
1195935osheeshKnapsack (NOI18_knapsack)C++20
73 / 100
1095 ms1608 KiB
#include <bits/stdc++.h> #define en '\n' #define sp ' ' #define ll long long #define pii pair<int, int> #define piii pair<int, pair<int, int>> #define maxx(a,b) a=max(a,b) #define minn(a,b) a=min(a,b) #define st first #define nd second using namespace std; const int N=1e5+5; ll dp[2005]; int v[N],w[N],k[N]; int main(){ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int wei,n; cin>>wei>>n; for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>k[i]; for(int i=1;i<=n;i++){ for(int j=1;k[i];j<<=1){ int cnt=min(j,k[i]); ll nv=1LL*v[i]*cnt,nw=1LL*w[i]*cnt; for(int curr=wei;curr>=nw;curr--) maxx(dp[curr],dp[curr-nw]+nv); k[i]-=cnt; } } cout<<dp[wei]; 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...