Josif_tepe

Untitled

Feb 9th, 2026
101
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. using namespace std;
  4. typedef long long ll;
  5. const int maxn = 1e5 + 10;
  6.  
  7. int n, d;
  8. ll P, a[maxn];
  9.  
  10. bool check(int K) {
  11.     priority_queue<ll> pq, greatest;
  12.     for(int i = 0; i < n; i++) {
  13.         pq.push(a[i]);
  14.     }
  15.    
  16.     ll sum = 0;
  17.     for(int i = 1; i <= d; i++) {
  18.         ll m = 0;
  19.         if(!pq.empty()) {
  20.             m = pq.top();
  21.             pq.pop();
  22.         }
  23.         sum += m;
  24.        
  25.         if(i > K) {
  26.             pq.push(greatest.top());
  27.             greatest.pop();
  28.         }
  29.         greatest.push(m);
  30.     }
  31.    
  32.     if(sum >= P) {
  33.         return true;
  34.     }
  35.     return false;
  36. }
  37. int main() {
  38.     cin >> n >> P >> d;
  39.    
  40.     for(int i = 0; i < n; i++) {
  41.         cin >> a[i];
  42.     }
  43.    
  44.     int L = 1;
  45.     int R = d;
  46.    
  47.     int res = -1;
  48.     while(L <= R) {
  49.         int middle = (L + R) / 2;
  50.        
  51.         if(check(middle)) {
  52.             res = max(res, middle);
  53.             L = middle + 1;
  54.         }
  55.         else {
  56.             R = middle - 1;
  57.         }
  58.        
  59.     }
  60.    
  61.     if(res == d) {
  62.         cout << "seedno" << endl;
  63.     }
  64.     else {
  65.         cout << res << endl;
  66.     }
  67.    
  68.     return 0;
  69. }
  70.  
Advertisement
Add Comment
Please, Sign In to add comment