Advertisement
Josif_tepe

Untitled

Mar 5th, 2024
778
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.21 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. //#include <bits/stdc++.h>
  5.  
  6. using namespace std;
  7. typedef long long ll;
  8. const int maxn = 1e5 + 10;
  9. int n, d;
  10. ll p;
  11. int v[maxn];
  12. bool check(int x) {
  13.     priority_queue<int> pq, greatest;
  14.     for(int i = 0; i < n; i++) {
  15.         pq.push(v[i]);
  16.     }
  17.     ll sum = 0;
  18.     for(int i = 1; i <= d; i++) {
  19.         int max_element = 0;
  20.         if(!pq.empty()) {
  21.             max_element = pq.top();
  22.             pq.pop();
  23.         }
  24.         sum += max_element;
  25.         if(i > x) {
  26.             pq.push(greatest.top());
  27.             greatest.pop();
  28.         }
  29.         greatest.push(max_element);
  30.     }
  31.     return sum >= p;
  32. }
  33. int main() {
  34.     ios_base::sync_with_stdio(false);
  35.     cin >> n >> p >> d;
  36.    
  37.    
  38.     for(int i = 0; i < n; i++) {
  39.         cin >> v[i];
  40.     }
  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 = max(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.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement