Advertisement
Josif_tepe

Untitled

Feb 29th, 2024
948
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.25 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. //#include <bits/stdc++.h>
  4. #include <cmath>
  5. #include <queue>
  6. #include <cstring>
  7. #include <algorithm>
  8. using namespace std;
  9. typedef long long ll;
  10. const int maxn = 1e5 + 10;
  11. int n, d;
  12. ll p;
  13. ll a[maxn];
  14. bool check(int k) {
  15.     ll sum = 0;
  16.     priority_queue<ll> pq, greatest;
  17.     for(int i = 0; i < n; i++) {
  18.         pq.push(a[i]);
  19.     }
  20.     for(int i = 1; i <= d; i++) {
  21.         ll max_tree = 0;
  22.         if(!pq.empty()) {
  23.             max_tree = pq.top();
  24.             pq.pop();
  25.         }
  26.         sum += max_tree;
  27.         if(i > k and !greatest.empty()) {
  28.             pq.push(greatest.top());
  29.             greatest.pop();
  30.         }
  31.         greatest.push(max_tree);
  32.     }
  33.     return sum >= p;
  34. }
  35. int main() {
  36.     ios_base::sync_with_stdio(false);
  37.     cin >> n >> p >> d;
  38.    
  39.     for(int i = 0; i < n; i++) {
  40.         cin >> a[i];
  41.     }
  42.     int L = 1, R = d;
  43.     int res = -1;
  44.     while(L <= R) {
  45.         int mid = (L + R) / 2;
  46.         if(check(mid)) {
  47.             L = mid + 1;
  48.             res = mid;
  49.         }
  50.         else {
  51.             R = mid - 1;
  52.         }
  53.     }
  54.     if(res == d) {
  55.         cout << "seedno" << endl;
  56.     }
  57.     else {
  58.         cout << res << endl;
  59.     }
  60.     return 0;
  61. }
  62.  
  63.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement