제출 #1167264

#제출 시각아이디문제언어결과실행 시간메모리
1167264constnodeKnapsack (NOI18_knapsack)C++20
73 / 100
1085 ms456 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int S, N; cin >> S >> N; // Use long long for dp to avoid overflow. vector<long long> dp(S + 1, 0); for (int i = 0; i < N; i++){ long long v, w; long long k; cin >> v >> w >> k; // Binary splitting: decompose the k copies into groups. long long amount = 1; while (k > 0) { long long use = min(amount, k); long long weight = w * use; long long value = v * use; // Process as a 0/1 knapsack item. for (int j = S; j >= weight; j--) { dp[j] = max(dp[j], dp[j - weight] + value); } k -= use; amount *= 2; } } 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...