Submission #1236519

#TimeUsernameProblemLanguageResultExecution timeMemory
1236519mirbek01Knapsack (NOI18_knapsack)C++20
73 / 100
462 ms327680 KiB
#include <bits/stdc++.h> using namespace std; int n, s; int main() { cin >> s >> n; vector < vector <int> > vec(s + 1); for (int i = 0; i < n; i++) { int v, w, k; cin >> v >> w >> k; k = min(k, s / w); for (int j = 0; j < k; j++) vec[w].push_back(v); } for (int i = 1; i <= s; i++) { sort(vec[i].rbegin(), vec[i].rend()); if (vec[i].size() > s / i) { vec[i].resize(s / i); } } 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:25:28: warning: overflow in conversion from 'double' to 'std::vector<int>::value_type' {aka 'int'} changes value from '-1.0e+18' to '-2147483648' [-Woverflow]
   25 |     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...