Submission #1261727

#TimeUsernameProblemLanguageResultExecution timeMemory
1261727mentariosKnapsack (NOI18_knapsack)C++20
73 / 100
1096 ms328 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define _ ios_base::sync_with_stdio(0); cin.tie(0); struct Item { ll w, v; }; int main() { _ int S, N; cin >> S >> N; vector<ll> dp(S + 1, 0); for (int i = 0; i < N; i++) { ll v, w, k; // Valor, Peso, Quantidade cin >> v >> w >> k; // Se o item é efetivamente ilimitado if (k * w >= S) { // Aplicamos a lógica do Knapsack ILIMITADO (loop para frente) for (int j = w; j <= S; j++) { dp[j] = max(dp[j], dp[j - w] + v); } } else { // Se o item é realmente limitado, usamos o splitting binário ll c = 1; while (k > c) { k -= c; ll current_w = c * w; ll current_v = c * v; // Aplicamos Knapsack 0/1 para cada pacote (loop para trás) for (int j = S; j >= current_w; j--) { dp[j] = max(dp[j], dp[j - current_w] + current_v); } c *= 2; } // Pacote final com o resto ll current_w = k * w; ll current_v = k * v; for (int j = S; j >= current_w; j--) { dp[j] = max(dp[j], dp[j - current_w] + current_v); } } } cout << dp[S] << endl; 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...