제출 #957299

#제출 시각아이디문제언어결과실행 시간메모리
957299ifateenKnapsack (NOI18_knapsack)C++17
73 / 100
1043 ms600 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int MAXS = 2005; int dp[MAXS]; void add(int weight, int value) { for (int i = MAXS - 1; i >= 0; --i) { if (i + weight < MAXS) dp[i + weight] = max(dp[i + weight], value + dp[i]); } } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); for (auto& i : dp) i = -1e18; dp[0] = 0; int n, s; cin >> s >> n; for (int i = 1; i <= n; ++i) { int value, weight, count; cin >> value >> weight >> count; count = min(count, s); int x = 1; while (count >= x) { add(weight * x, value * x); count -= x; x *= 2; } if (count) add(weight * count, value * count); } cout << *max_element(dp, dp + s + 1); }
#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...