Submission #1205072

#TimeUsernameProblemLanguageResultExecution timeMemory
1205072jenterjongle45Knapsack (NOI18_knapsack)C++20
73 / 100
1096 ms328 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; using pii=pair<ll,ll>; const int N=2020; int s,n; ll dp[N]; void calc(ll v,ll w){ for(int i=s;i>=w;i--){ dp[i]=max(dp[i],dp[i-w]+v); } } int main(){ cin.tie(0)->sync_with_stdio(0); cin>>s>>n; for(int i=0;i<n;i++){ ll v,w,k,now=1,kk;cin>>v>>w>>k; kk=k; while(now<=kk&&kk>0&&now*w<=s){ calc(v*now,w*now); kk-=now; now<<=1; } if(kk>0&&kk*w<=s) calc(v*kk,kk*w); } cout<<dp[s]; }
#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...