제출 #808804

#제출 시각아이디문제언어결과실행 시간메모리
808804GoldLightKnapsack (NOI18_knapsack)C++17
73 / 100
1085 ms1332 KiB
#include <bits/stdc++.h> using namespace std; void fast(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);} const int N=2e3; long long dp[N+1]; int main(){ fast(); int s, n, v, w, k; cin>>s>>n; for(int i=1; i<=n; i++){ cin>>v>>w>>k; for(int j=s; j>=1; j--){ for(int l=1; l<=k; l++){ if(j<w*l) break; dp[j]=max(dp[j], dp[j-w*l]+1ll*v*l); } } } 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...