This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
int32_t main() {
int32_t S, N;
std::cin >> S >> N;
std::vector<int64_t> dp(S + 1, -1);
dp[0] = 0;
std::vector<std::vector<std::pair<int32_t, int32_t>>> wCnt(S + 1, std::vector<std::pair<int32_t, int32_t>>());
for(int32_t i = 0; i < N; i++) {
int32_t V, W, K;
std::cin >> V >> W >> K;
wCnt[W].push_back({V, K});
}
for(int32_t i = 0; i < N; i++) {
sort(wCnt[i].begin(), wCnt[i].end(), std::greater<std::pair<int32_t, int32_t>>());
}
std::vector<std::vector<std::pair<int32_t, int32_t>>> kCnt(S + 1, std::vector<std::pair<int32_t, int32_t>>(S + 1));
std::vector<int32_t> take(S + 1);
for(int32_t j = 0; j < S; j++) {
if(j != 0) {
for(int32_t i = 1; i <= S; i++) {
if(wCnt[i].size() == 0) continue;
if(i != take[j]) kCnt[j][i] = kCnt[j - take[j]][i];
else {
kCnt[j][i].first = kCnt[j - take[j]][i].first + 1;
kCnt[j][i].second = kCnt[j - take[j]][i].second;
if(kCnt[j][i].first >= wCnt[i][kCnt[j][i].second].second) {
kCnt[j][i].first = 0;
kCnt[j][i].second++;
// std::cout << "kill me\n";
// std::cout << kCnt[j][i].first << " " << kCnt[j][i].second << "\n";
}
if(kCnt[j][i].second >= wCnt[i].size()) {
// std::cout << "something WRONG IS HAPPENING\n";
kCnt[j][i] = {-1, -1};
}
}
}
}
if(dp[j] == -1) continue;
for(int i = 1; i <= S; i++) {
if(j + i > S) break;
if(wCnt[i].size() == 0 || kCnt[j][i].second == -1) continue;
if(dp[i + j] < dp[j] + wCnt[i][kCnt[j][i].second].first) {
// std::cout << "before: " << dp[i + j] << "\n";
dp[i + j] = dp[j] + wCnt[i][kCnt[j][i].second].first;
// std::cout << "after: " << dp[i + j] << "\n";
// std::cout << dp[j] << " " << wCnt[i][kCnt[j][i].second].first << "\n";
// std::cout << "dp[i + j]: " << "i = " << i << ", j = " << j << " = " << dp[i + j] << "\n";
take[i + j] = i;
}
}
}
int64_t ans = 0;
for(int32_t i = 0; i <= S; i++) {
// std::cout << i << ": " << dp[i] << " " << take[i] << "\n";
if(dp[i] != -1) ans = std::max(ans, dp[i]);
}
// std::cout << "\n";
std::cout << ans << "\n";
return 0;
}
Compilation message (stderr)
knapsack.cpp: In function 'int32_t main()':
knapsack.cpp:33:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | if(kCnt[j][i].second >= wCnt[i].size()) {
# | 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... |