Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
1.4 kB
2
Indexable
Never
#include <bits/stdc++.h>

using namespace std;

vector < pair<int,int> > auti;

vector <int> benze;

int main(){
	long long n, k, s, t, c, v, g;
	cin>>n>>k>>s>>t;
	
	for (int i = 0; i < n; i++){
		cin>>c>>v;
		auti.push_back(make_pair(c,v));
	}
	
	for (int i = 0; i < k; i++){
		cin>>g;
		benze.push_back(g);
	}
	
	sort(benze.begin(),benze.end());
	
	int potrebnoAcc = s * 2 - t, postojiAuto = 0;
	
	int l = 1, r = 1e9, mid, razmak, istina = 1;
	while (l<r){
		mid = (l + r)/2;
		istina = 1;
		potrebnoAcc = s * 2 - t;
		
		for (int i = 0; i < k; i++){
			if (i == 0){
				razmak = benze[i];
			}
			else{
				razmak = benze[i] - benze[i - 1];
			}
			
			if (mid >= razmak) potrebnoAcc -= min(razmak,mid-razmak);
			else istina = 0;
			
		}
		
		if (mid >= s - benze[k-1]) potrebnoAcc -= min(s - benze[k - 1],mid - (s - benze[k - 1]));
		else istina = 0;
		
		//if (mid == 7) cout << razmak<<endl;
		
		if (istina == 1 && potrebnoAcc <= 0 ) {
			r = mid - 1;
			postojiAuto = 1;
		}
		else l = mid + 1;
		
		//cout<<"MID = "<<mid<<endl;
	}
	
	if (!postojiAuto){
		cout<<-1;
		return 0;
	}
	
	int mini = 1e9;
	int postoji = 0;
	
	for (int i = 0; i < n; i++){
		if (auti[i].second >= mid){
			postoji = 1;
			mini = min(auti[i].first,mini);
		}
	}

	if (postoji) cout<<mini;	
	else cout<<-1;
	
	return 0;
}