Submission #1140174

#TimeUsernameProblemLanguageResultExecution timeMemory
1140174hemaprakashKnapsack (NOI18_knapsack)C++20
17 / 100
1 ms396 KiB
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int s, n; cin >> s >> n; vector<long long> dp(s + 1); dp[0] = 0; for (int i = 0; i < n; i++) { int v, w, k; cin >> v >> w >> k; for (int j = s; j >= w; j--) { int lo = 1, hi = k; while (lo <= hi) { int mid = (lo + hi) / 2; int weight = mid * w; if (weight > s) { hi = mid - 1; } else { long long price = 1LL * mid * v + dp[j - weight]; if (price >= dp[j]) { dp[j] = price; lo = mid + 1; } else { hi = mid - 1; } } } } } 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...