Submission #1189264

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