Advertisement
Josif_tepe

Untitled

Apr 22nd, 2023
737
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.89 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstring>
  3. #include <vector>
  4. #include <queue>
  5. #include <algorithm>
  6. using namespace std;
  7. const int maxn = 1005;
  8.  
  9. int main() {
  10.     ios_base::sync_with_stdio(false);
  11.     int t;
  12.     cin >> t;
  13.    
  14.     while(t--) {
  15.         int n;
  16.         cin >> n;
  17.         int result = 0;
  18.         vector<int> dist(n), gas(n);
  19.         for(int i = 0; i < n; i++) {
  20.             cin >> dist[i] >> gas[i];
  21.         }
  22.         int city_distance, fuel;
  23.         cin >> city_distance >> fuel;
  24.        
  25.         vector<pair<int, int>> gas_stations;
  26.         priority_queue<int> gas_available;
  27.         for(int i = 0; i < n; i++) {
  28.             gas_stations.push_back(make_pair(city_distance - dist[i], gas[i]));
  29.         }
  30.         gas_stations.push_back(make_pair(city_distance, 0));
  31.         sort(gas_stations.begin(), gas_stations.end());
  32.         int location = 0;
  33.         bool ok = true;
  34.         for(int i = 0; i < gas_stations.size(); i++) {
  35.             int distance_from_gas_station = gas_stations[i].first - location;
  36.            
  37.             if(distance_from_gas_station > fuel) {
  38.                 while(distance_from_gas_station > fuel) {
  39.                     if(gas_available.empty()) {
  40.                         cout << -1 << endl;
  41.                         ok = false;
  42.                         break;
  43.                     }
  44.                     int max_available_gas = gas_available.top();
  45.                     gas_available.pop();
  46.                     fuel += max_available_gas;
  47.                     result++;
  48.                 }
  49.                 if(!ok) {
  50.                     break;
  51.                 }
  52.             }
  53.             fuel -= distance_from_gas_station;
  54.             location = gas_stations[i].first;
  55.             gas_available.push(gas_stations[i].second);
  56.            
  57.         }
  58.         if(ok) {
  59.             cout << result << endl;
  60.         }
  61.        
  62.     }
  63.    
  64.  
  65.     return 0;
  66. }
  67.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement