Submission #1205074

#TimeUsernameProblemLanguageResultExecution timeMemory
1205074jenterjongle45Knapsack (NOI18_knapsack)C++20
37 / 100
1 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,dp[N]; void calc(int v,int 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++){ int v,w,k,now=1,kk;cin>>v>>w>>k; kk=k; while(now<=kk&&kk>0&&ll(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...