fork download
  1.  
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define mod 1000000007
  5. #define rep(i, n) for(int i = 0; i < n; i++)
  6. #define rep1(i,a,b) for(int i=a;i<b;i++)
  7. #define endl "\n"
  8. #define PI 3.14159265358979323846 /* pi */
  9. #define is_pot(n) (n&& !(n&(n-1)))
  10. #define all(v) ((v).begin()),((v).end())
  11. #define int long long
  12. #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
  13. #define epsilon 1e-9
  14. typedef long long ll;
  15. typedef long double ld;
  16.  
  17. int dx[]={1, 0, -1, 0};
  18. int dy[]={0, 1, 0, -1};
  19.  
  20.  
  21.  
  22.  
  23.  
  24.  
  25.  
  26.  
  27.  
  28.  
  29.  
  30.  
  31.  
  32.  
  33.  
  34.  
  35.  
  36.  
  37. vector<pair<int, int>> v;
  38. int L, P;
  39.  
  40. void solve()
  41. {
  42. int n;
  43. cin>>n;
  44.  
  45. rep(i, n)
  46. {
  47. int d, p;
  48. cin>>d>>p;
  49. v.push_back({d, p});
  50. }
  51.  
  52. v.push_back({0, 0});
  53. n++;
  54.  
  55. cin>>L>>P;
  56.  
  57. sort(all(v));
  58. reverse(all(v));
  59.  
  60. if(P>=L)
  61. {
  62. cout<<0<<endl;
  63. return;
  64. }
  65.  
  66. priority_queue<int> pq;
  67.  
  68. int fuel=P, cnt=0;
  69.  
  70. fuel-=(L-v[0].first);
  71.  
  72. if(fuel<0)
  73. {
  74. cout<<-1<<endl;
  75. return;
  76. }
  77.  
  78. for(int i=0;i<n-1;i++)
  79. {
  80. pq.push(v[i].second);
  81. while(!pq.empty() && fuel<(v[i].first-v[i+1].first))
  82. {
  83. fuel+=pq.top();
  84. pq.pop();
  85. cnt++;
  86. }
  87. if(pq.empty() && fuel<(v[i].first-v[i+1].first))
  88. {
  89. cout<<-1<<endl;
  90. return;
  91. }
  92. fuel-=(v[i].first-v[i+1].first);
  93. }
  94.  
  95. cout<<cnt<<endl;
  96.  
  97. }
  98.  
  99. signed main() {
  100.  
  101. fastio
  102.  
  103. int t;cin>>t;while(t--)
  104. solve();
  105.  
  106.  
  107. return 0;
  108. }
Runtime error #stdin #stdout 2.26s 2095884KB
stdin
Standard input is empty
stdout
Standard output is empty