제출 #491324

#제출 시각아이디문제언어결과실행 시간메모리
491324DDTerziev04Knapsack (NOI18_knapsack)C++14
73 / 100
1088 ms2720 KiB
#include<iostream> using namespace std; const int MAXN=1e5, MAXS=2000; int dp[MAXS+1]; int p[MAXN], w[MAXN], h[MAXN]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int s, n; cin >> s >> n; for(int i=0; i<n; i++) { cin >> p[i] >> w[i] >> h[i]; } for(int i=0; i<=s; i++) { dp[i]=-1; } dp[0]=0; int ans=0; for(int i=0; i<n; i++) { for(int j=s; j>=0; j--) { for(int u=1; u<=h[i] && u*w[i]<=j; u++) { if(dp[j-u*w[i]]==-1) { continue; } dp[j]=max(dp[j], dp[j-u*w[i]]+u*p[i]); } ans=max(ans, dp[j]); } } cout << ans << "\n"; 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...