Участник:Andriygav/EXPEDI

Материал из DISCOPAL
Перейти к: навигация, поиск

ссылка: https://www.spoj.com/problems/EXPEDI/


#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
 
size_t id[16384], fuel[16384], dist[16384], L, P;
 
struct comparator {
    bool operator ()(const int &a, const int &b){
        if(fuel[a] == fuel[b])
            return false;
        return fuel[a]<fuel[b];
    }
};
 
struct comp{
    bool operator ()(const int &a, const int &b){
        if(dist[a] == dist[b])
            return false;
        return dist[a] < dist[b];
    }
};
 
priority_queue<int, vector<int>, comparator> pq;
 
int main() {
    size_t cur;
    int t, ans;
 
    cin >> t;
    while(t--){
    	int n;
        cin >> n;
        for(int i = 0; i < n; i++){
            cin >> dist[i] >> fuel[i];
            id[i] = i;
        }
        cin >> L >> P;
 
        for(int i = 0; i < n; i++){
        	dist[i] = L - dist[i];
        }
 
        if(P >= L){
        	ans = 0;
        }else{
        	sort(id, id + n, comp());
        	while(!pq.empty()){
        		 pq.pop();
        	}
 
        	bool ok = true;
        	size_t cur = 0;
        	ans = 0;
 
        	for(int i = 0; i < n; i++){
        		if (L - cur <= P) {
        			break;
        		}
 
        		if(dist[id[i]] - cur <= P){
        			P -= (dist[id[i]] - cur);
        			cur = dist[id[i]];
        			pq.push(id[i]);
        			continue;
        		}
 
        		while(!pq.empty() && P < dist[id[i]] - cur && !(P >= L - cur)){
	                ans++;
	                P += fuel[pq.top()];
	                pq.pop();
	            }
	            if(P >= L - cur){
	                break;
	            }
	            if(P < dist[id[i]] - cur){
	                ok = false;
	                break;
	            }
	            P -= (dist[id[i]]-cur);
	            cur = dist[id[i]];
	            pq.push(id[i]);
        	}
        	if(!ok) {
	            ans = -1;
	        }else if(cur < L){
	        	while(!pq.empty() && P < L-cur){
	            	ans++;
	            	P += fuel[pq.top()];
	            	pq.pop();
	            }
	            if(P < L - cur){
	            	ok = false;
	            }
	            else{
	            	cur = L;
	            }
	        }else if(cur < L){
	        	ok = false;
	        }else if(!ok) {
	            ans = -1;
	        }
        }
        cout << ans << endl;
    }
 
    return 0;
}