Submission #1236531

#TimeUsernameProblemLanguageResultExecution timeMemory
1236531mirbek01Knapsack (NOI18_knapsack)C++20
100 / 100
75 ms1656 KiB
#include <bits/stdc++.h> using namespace std; int n, s; int main() { cin >> s >> n; vector < vector <pair <int, int>> > vc(s + 1); for (int i = 0; i < n; i++) { int v, w, k; cin >> v >> w >> k; vc[w].push_back({v, k}); } vector < vector <int> > vec(s + 1); for (int i = 1; i <= s; i++) { sort(vc[i].rbegin(), vc[i].rend()); int kol = s / i; for (auto [val, cnt] : vc[i]) { int mn = min(kol, cnt); for (int j = 0; j < mn; j++) { vec[i].push_back(val); } kol -= mn; } } vector <int> dp(s + 1, -1e18); dp[0] = 0; for (int w = 1; w <= s; w++) { for (int x : vec[w]) { for (int W = s; W >= w; W--) { dp[W] = max(dp[W], dp[W - w] + x); } } } int ans = 0; for (int i = 1; i <= s; i++) ans = max(ans, dp[i]); cout << ans << endl; }

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:30:28: warning: overflow in conversion from 'double' to 'std::vector<int>::value_type' {aka 'int'} changes value from '-1.0e+18' to '-2147483648' [-Woverflow]
   30 |     vector <int> dp(s + 1, -1e18);
      |                            ^~~~~
#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...