Submission #1184020

#TimeUsernameProblemLanguageResultExecution timeMemory
1184020ayushtiwari110Knapsack (NOI18_knapsack)C++20
73 / 100
1095 ms1984 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int S, N; cin >> S >> N; vector<tuple<int, int, int>> items; // (value, weight, count) for (int i = 0; i < N; i++) { int V, W, K; cin >> V >> W >> K; items.push_back({V, W, K}); } // dp[w] = maximum value possible with weight w vector<long long> dp(S + 1, 0); for (auto [value, weight, count] : items) { // Skip items that are too heavy if (weight > S) continue; // Process from right to left to avoid using the same item multiple times for (int w = S; w >= weight; w--) { // Try using j copies of current item for (int j = 1; j <= count && j * weight <= w; j++) { dp[w] = max(dp[w], dp[w - j * weight] + j * (long long)value); } } } 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...