Samkit5025

Untitled

Sep 13th, 2022
56
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.82 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int binarySearch(vector<int> &pref,int n,int left){
  5.     int start =0;
  6.     int end = n-1;
  7.     int ans = -1;
  8.  
  9.     while(start<=end){
  10.         int mid = (start+end)/2;
  11.         if(pref[mid]>=left){
  12.             ans = mid;
  13.             end = mid-1;
  14.         }
  15.         else{
  16.             start = mid+1;
  17.         }
  18.     }
  19.     return ans;
  20. }
  21.  
  22. int minimumPriorityQuotient(int N,int L,vector<int> &P,vector<int> &PQ){
  23.  
  24.     int sum =0;
  25.     for(int i=0;i<N;i++){
  26.         sum+=P[i];
  27.     }
  28.  
  29.     if(sum<L){
  30.         return -1;
  31.     }                          
  32.  
  33.     vector<int> not_rare;
  34.     vector<int> rare;
  35.  
  36.     for(int i=0;i<N;i++){
  37.    
  38.         if(PQ[i]==1){
  39.             not_rare.push_back(P[i]);
  40.         }
  41.         else{
  42.             rare.push_back(P[i]);
  43.         }
  44.     }
  45.  
  46.     sort(not_rare.begin(),not_rare.end(),greater<int>());
  47.     sort(rare.begin(),rare.end(),greater<int>());
  48.  
  49.     vector<int> pref(rare.size()+1);
  50.    
  51.     for(int i=0;i<pref.size()-1;i++){
  52.         pref[i+1] = pref[i] + rare[i];
  53.     }
  54.  
  55.     int ans = 100000;
  56.  
  57.     int pos = binarySearch(pref,pref.size(),L);
  58.     if(pos!=-1){
  59.         ans = min(ans,2*pos);
  60.     }
  61.  
  62.     int totalMem = 0;
  63.    
  64.     for(int i=0;i<not_rare.size();i++){
  65.         int temp = i+1;
  66.         totalMem+=not_rare[i];
  67.         int left = L-totalMem;
  68.         if(left){
  69.             pos = binarySearch(pref,pref.size(),left);
  70.             if(pos==-1){
  71.                 continue;
  72.             }
  73.             temp+=(2*pos);
  74.         }
  75.         ans = min(ans,temp);
  76.     }
  77.     return ans;
  78. }
  79.  
  80. signed main() {
  81.    
  82.     int N;
  83.     int L;
  84.     cin>>N>>L;
  85.     vector<int> P(N);
  86.     vector<int> PQ(N);
  87.  
  88.     for(int i=0;i<N;i++)cin>>P[i];
  89.     for(int i=0;i<N;i++)cin>>PQ[i];
  90.     cout<<minimumPriorityQuotient(N,L,P,PQ)<<endl;
  91.  
  92. }
Advertisement
Add Comment
Please, Sign In to add comment