Submission #1193690

#TimeUsernameProblemLanguageResultExecution timeMemory
1193690SulAKnapsack (NOI18_knapsack)C++20
73 / 100
1087 ms528 KiB
#include <bits/stdc++.h> #define all(a) a.begin(), a.end() #define popcount(x) __builtin_popcountll(x) using namespace std; using namespace chrono; long long dp[2001]; void add(long long val, long long cost) { for (int i = 2000; i >= cost; i--) dp[i] = max(dp[i], dp[i - cost] + val); } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n,s; cin >> s >> n; for (int i = 0; i < n; i++) { long long val, cost, k; cin >> val >> cost >> k; int b = 1; while (k >= b) { add(val*b, cost*b); k -= b; b <<= 1; } add(val*k, cost*k); } cout << dp[s]; }
#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...