Submission #1236523

#TimeUsernameProblemLanguageResultExecution timeMemory
1236523mirbek01Knapsack (NOI18_knapsack)C++20
73 / 100
1095 ms584 KiB
#include <bits/stdc++.h> using namespace std; int n, s; int main() { cin >> s >> n; vector < multiset <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].insert(v); if (vec[w].size() > s / w) { vec[w].erase(vec[w].begin()); } } } vector <int> dp(s + 1, -1e18); dp[0] = 0; for (int w = 1; w <= s; w++) { for (auto 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:23:28: warning: overflow in conversion from 'double' to 'std::vector<int>::value_type' {aka 'int'} changes value from '-1.0e+18' to '-2147483648' [-Woverflow]
   23 |     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...