Josif_tepe

Untitled

Jan 28th, 2026
140
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.20 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. typedef long long ll;
  8. const int maxn = 1e5 + 10;
  9. int n, d;
  10. ll P;
  11. vector<ll> a(maxn);
  12.  
  13. bool check(int K) {
  14.     priority_queue<ll> pq, greatest;
  15.     for(int i = 0; i < n; i++) {
  16.         pq.push(a[i]);
  17.     }
  18.  
  19.     ll sum = 0;
  20.     for(int i = 1; i <= d; i++) {
  21.         ll max_element = 0;
  22.         if(!pq.empty()) {
  23.             max_element = pq.top();
  24.             pq.pop();
  25.         }
  26.  
  27.         sum += max_element;
  28.         if(i > K) {
  29.             pq.push(greatest.top());
  30.             greatest.pop();
  31.         }
  32.  
  33.         greatest.push(max_element);
  34.  
  35.     }
  36.  
  37.     if(sum >= P) {
  38.         return true;
  39.     }
  40.     return false;
  41.  
  42. }
  43. int main() {
  44.  
  45.     cin >> n >> P >> d;
  46.     for(int i = 0; i < n; i++) {
  47.         cin >> a[i];
  48.     }
  49.    
  50.     int l=1,r=d,res=-1;
  51.     while(l<=r)
  52.     {
  53.         int mid=(l+r)/2;
  54.         if(check(mid))
  55.         {
  56.             res=max(res, mid);
  57.             l=mid+1;
  58.         }
  59.         else
  60.         {
  61.             r=mid-1;
  62.         }
  63.     }
  64.    
  65.     if(res == d) {
  66.         cout << "seedno" << endl;
  67.     }
  68.     else {
  69.         cout<<res << endl;
  70.     }
  71.    
  72.         return 0;
  73. }
  74.  
Advertisement
Add Comment
Please, Sign In to add comment