Submission #1020198

#TimeUsernameProblemLanguageResultExecution timeMemory
1020198ArthuroWichKnapsack (NOI18_knapsack)C++17
100 / 100
81 ms5212 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int void solve() { int s, n; cin >> s >> n; vector<int> dp(s+1, -1); dp[0] = 0; set<int> weights; map<int, vector<pair<int, int>>> items; for (int i = 0; i < n; i++) { int v, w, k; cin >> v >> w >> k; weights.insert(w); items[w].push_back({v, k}); } for (int w : weights) { sort(items[w].rbegin(), items[w].rend()); int total = 0; for (int i = 0; i < items[w].size() && total <= 2000; i++) { int l; auto [v, k] = items[w][i]; total += k*w; while(k > 0) { l = log2(k); if (l != 0) { k -= (1<<l)-1; } else { k--; l++; } for (int x = 0; x < l; x++) { if ((1LL<<x)*w > 2000) { break; } for (int j = s; j >= 0; j--) { if (j-(1LL<<x)*w < 0) { break; } if (dp[j-(1LL<<x)*w] != -1) { dp[j] = max(dp[j], dp[j-(1LL<<x)*w]+(1LL<<x)*v); } } } } } } int ans = 0; for (int i : dp) { ans = max(ans, i); } cout << ans << endl; } int32_t main() { ios::sync_with_stdio(0); cin.tie(0); int t; t = 1; while(t--) { solve(); } }

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:20:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         for (int i = 0; i < items[w].size() && total <= 2000; i++) {
      |                         ~~^~~~~~~~~~~~~~~~~
#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...