제출 #1048851

#제출 시각아이디문제언어결과실행 시간메모리
1048851tamir1Knapsack (NOI18_knapsack)C++17
73 / 100
1029 ms2660 KiB
#include<bits/stdc++.h> #define ll long long using namespace std; ll n,S,i,j,l,res,dp[2005],s[100001],w[100001],k[100001]; int main(){ cin >> S >> n; for(i=1;i<=n;i++){ cin >> s[i] >> w[i] >> k[i]; } for(i=1;i<=n;i++){ for(l=S;l>=w[i];l--){ for(j=1;j<=k[i];j++){ if(l-w[i]*j<0) break; dp[l]=max(dp[l],dp[l-w[i]*j]+s[i]*j); } } } for(i=0;i<=S;i++) res=max(res,dp[i]); cout << res; }
#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...