Submission #1195954

#TimeUsernameProblemLanguageResultExecution timeMemory
1195954osheeshKnapsack (NOI18_knapsack)C++20
73 / 100
1091 ms1632 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++){ if(w[i]>wei) continue; int tmp=min(k[i],wei/w[i]); for(int j=1;tmp;j<<=1){ int cnt=min(j,tmp); 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); tmp-=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...