Advertisement
Josif_tepe

Untitled

Mar 3rd, 2024
740
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.29 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <iomanip>
  5. #include <cstring>
  6. #include <queue>
  7. #include <set>
  8. #include <cmath>
  9. #define ll long long
  10. using namespace std;
  11. int arr[100005];
  12. int n,d;
  13. ll p;
  14.  
  15.  
  16. int f(int k){
  17.     priority_queue<int>pq;
  18.     priority_queue<int>iseceni;
  19.     for(int i = 0;i<n;i++){
  20.         pq.push(arr[i]);
  21.     }
  22.     ll sum =0;
  23.     for(int i =1;i<=d;i++){
  24.         int najgolemo = 0;
  25.         if(!pq.empty()) {
  26.             najgolemo = pq.top();
  27.             pq.pop();
  28.         }
  29.             sum+= najgolemo;
  30.             if(i>k and !iseceni.empty()){
  31.                 pq.push(iseceni.top());
  32.                 iseceni.pop();
  33.             }
  34.             iseceni.push(najgolemo);
  35.        
  36.     }
  37.    
  38.     if(sum >= p) return 1;
  39.     else return  -1;
  40. }
  41. int main() {
  42.    
  43.     cin >> n >> p >>d;
  44.     for(int i =0;i<n;i++){
  45.         cin >> arr[i];
  46.     }
  47.    
  48.     int left,right,mid;
  49.     left = 0;
  50.     right = d;
  51.     int res = -1;
  52.     while(left <= right){
  53.         mid = (left+right)/2;
  54.         if(f(mid) == 1){
  55.             left= mid+1;
  56.             res = max(res,mid);
  57.         }
  58.         else if(f(mid) == -1){
  59.             right=mid-1;
  60.         }
  61.     }
  62.    
  63.    
  64.     if(res == d){
  65.         cout << "seedno";
  66.     }
  67.     else cout << res;
  68. }
  69.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement