Submission #1189281

#TimeUsernameProblemLanguageResultExecution timeMemory
1189281thien_ngaKnapsack (NOI18_knapsack)C++20
73 / 100
1095 ms17784 KiB
#include<bits/stdc++.h> using namespace std; typedef long long LL; int main() { ios_base::sync_with_stdio(0); cin.tie(0); LL n, i, j, X; cin >> X >> n; vector <LL> price, value; LL h[n], s[n]; for (i = 0; i < n; i++) { LL x; cin >> s[i] >> h[i] >> x; j = 1; while (x >= j) { price.push_back(h[i] * j); value.push_back(s[i] * j); x -= j; j *= 2; } if (x > 0) { price.push_back(h[i] * x); value.push_back(s[i] * x); } } n = price.size(); vector <LL> dp (X+1); for (i = 0; i < n; i++) for (j = X; j >= price[i]; j--) dp[j] = max (dp[j], dp[j-price[i]] + value[i]); cout << dp[X] << "\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...