fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/JZnabq
language:
C++14 (gcc 8.3)
created:
2 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!