이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define fi first
#define se second
#define sz(v) int(v.size())
int main() {
int lim, n;
cin >> lim >> n;
map<int, vector<pii>> list_of_items;
for (int i = 0; i < n; i++) {
int val, weight, cnt;
cin >> val >> weight >> cnt;
list_of_items[weight].emplace_back(val, cnt);
}
vector<vector<ll>> dp(sz(list_of_items) + 1, vector<ll>(lim + 1, -1000));
dp[0][0] = 0;
int i = 1;
for (auto &[weight, items] : list_of_items) {
sort(items.begin(), items.end(), greater<pii>());
for (int j = 0; j <= lim; j++) {
dp[i][j] = dp[i - 1][j];
int cps = 0, items_idx = 0, used = 0;
long long profit = 0;
while ((cps + 1) * weight <= j && items_idx < sz(items)) {
cps++;
profit += items[items_idx].fi;
if (dp[i - 1][j - cps * weight] != -1000) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - cps * weight] + profit);
}
used++;
if (used == items[items_idx].se) {
used = 0, items_idx++;
}
}
}
i++;
}
cout << *max_element(dp.back().begin(), dp.back().end()) << '\n';
}
컴파일 시 표준 에러 (stderr) 메시지
knapsack.cpp: In function 'int main()':
knapsack.cpp:21:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
21 | for (auto &[weight, items] : list_of_items) {
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |