Submission #1218180

#TimeUsernameProblemLanguageResultExecution timeMemory
1218180shuvo_06Knapsack (NOI18_knapsack)C++20
73 / 100
165 ms327680 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int32_t main() { ios::sync_with_stdio(false); cin.tie(0); int S, N; cin >> S >> N; vector<pair<int, int>> obj; for (int i = 0; i < N; i++) { int val, wt, copies; cin >> val >> wt >> copies; for (int p = 1; copies; p <<= 1) { int take = min(p, copies); obj.emplace_back(take * wt, take * val); copies -= take; } } int M = obj.size(); vector<vector<int>> dp(M + 1, vector<int>(S + 1, 0)); for (int i = 1; i <= M; i++) { auto [wt, val] = obj[i - 1]; for (int cap = 0; cap <= S; cap++) { dp[i][cap] = dp[i - 1][cap]; if (cap >= wt) dp[i][cap] = max(dp[i][cap], dp[i - 1][cap - wt] + val); } } cout << *max_element(dp[M].begin(), dp[M].end()) << "\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...