fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4. bool compare(pair<ll,ll>p1,pair<ll,ll>p2){
  5.     return p1.first>p2.first;
  6. }
  7. int main(){
  8.     ll n,t,x,d,f,D,F,prev = 0;
  9.     cin>>t;
  10.     while(t--){
  11.         ll flag = 0,ans = 0;
  12.         vector<pair<ll,ll>>v;
  13.         priority_queue<ll>pq;
  14.         cin>>n;
  15.         for (ll i = 0; i < n; i++)
  16.         {
  17.             cin>>d>>f;
  18.             v.push_back(make_pair(d,f));
  19.         }
  20.         sort(v.begin(),v.end(),compare);
  21.         cin>>D>>F;
  22.         for(ll i=0;i<n;i++){
  23.             v[i].first = D - v[i].first;
  24.         }
  25.         prev = 0;
  26.         x = 0;
  27.         while(x<n){
  28.             if(F >= (v[x].first - prev)){
  29.                 F-=(v[x].first - prev);
  30.                 pq.push(v[x].second);
  31.                 prev = v[x].first;
  32.  
  33.             }else{
  34.                 if(pq.empty()){
  35.                     flag = 1;
  36.                     break;
  37.                 }
  38.                 F += pq.top();
  39.                 pq.pop();
  40.                 ans+=1;
  41.                 continue;
  42.             }
  43.             x++;
  44.         }
  45.         if(flag == 1){
  46.             cout<<-1<<endl;
  47.             continue;
  48.         }
  49.  
  50.         D = D - v[n-1].first;
  51.         if(F>=D){
  52.             cout<<ans<<endl;
  53.             continue;
  54.         }
  55.         while(F<D){
  56.             if(pq.empty()){
  57.                 flag = 1;
  58.                 break;
  59.             }
  60.             F += pq.top();
  61.             pq.pop();
  62.             ans++;
  63.         }
  64.  
  65.         if(flag==1){
  66.             cout<<-1<<endl;
  67.             continue;
  68.         }
  69.         cout<<ans<<endl;
  70.  
  71.  
  72.     }
  73.     return 0;
  74. }
Time limit exceeded #stdin #stdout 5s 4197624KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/A74Hv5
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!