제출 #938885

#제출 시각아이디문제언어결과실행 시간메모리
938885myst6Knapsack (NOI18_knapsack)C++14
73 / 100
1052 ms424 KiB
#include <bits/stdc++.h> using namespace std; #define int long long signed main() { cin.tie(0)->sync_with_stdio(0); int S, N; cin >> S >> N; vector<int> dp(S+1); for (int i=0; i<N; i++) { int V, W, K; cin >> V >> W >> K; for (int j=0; K>=(1<<j); j++) { int v = V << j; int w = W << j; for (int k=S-w; k>=0; k--) { dp[k+w] = max(dp[k+w], dp[k]+v); } K -= 1 << j; if (K & (1 << j)) { for (int k=S-w; k>=0; k--) { dp[k+w] = max(dp[k+w], dp[k]+v); } K -= 1 << j; } } } cout << dp[S] << "\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...