Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int binarySearch(vector<int> &pref,int n,int left){
- int start =0;
- int end = n-1;
- int ans = -1;
- while(start<=end){
- int mid = (start+end)/2;
- if(pref[mid]>=left){
- ans = mid;
- end = mid-1;
- }
- else{
- start = mid+1;
- }
- }
- return ans;
- }
- int minimumPriorityQuotient(int N,int L,vector<int> &P,vector<int> &PQ){
- int sum =0;
- for(int i=0;i<N;i++){
- sum+=P[i];
- }
- if(sum<L){
- return -1;
- }
- vector<int> not_rare;
- vector<int> rare;
- for(int i=0;i<N;i++){
- if(PQ[i]==1){
- not_rare.push_back(P[i]);
- }
- else{
- rare.push_back(P[i]);
- }
- }
- sort(not_rare.begin(),not_rare.end(),greater<int>());
- sort(rare.begin(),rare.end(),greater<int>());
- vector<int> pref(rare.size()+1);
- for(int i=0;i<pref.size()-1;i++){
- pref[i+1] = pref[i] + rare[i];
- }
- int ans = 100000;
- int pos = binarySearch(pref,pref.size(),L);
- if(pos!=-1){
- ans = min(ans,2*pos);
- }
- int totalMem = 0;
- for(int i=0;i<not_rare.size();i++){
- int temp = i+1;
- totalMem+=not_rare[i];
- int left = L-totalMem;
- if(left){
- pos = binarySearch(pref,pref.size(),left);
- if(pos==-1){
- continue;
- }
- temp+=(2*pos);
- }
- ans = min(ans,temp);
- }
- return ans;
- }
- signed main() {
- int N;
- int L;
- cin>>N>>L;
- vector<int> P(N);
- vector<int> PQ(N);
- for(int i=0;i<N;i++)cin>>P[i];
- for(int i=0;i<N;i++)cin>>PQ[i];
- cout<<minimumPriorityQuotient(N,L,P,PQ)<<endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment