Advertisement
og86

sort h soln

Dec 19th, 2022
3,591
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.04 KB | Source Code | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define ll long long
  5. #define el '\n'
  6. #define yes cout<<"YES"<<el
  7. #define no cout<<"NO"<<el
  8. #define f(i,a,b) for(ll i = a; i <= b; i++)
  9. #define fr(i,a,b) for(ll i = a; i >= b; i--)
  10. #define vi vector<int>
  11. #define speed ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0)
  12. #define pb push_back
  13. #define all(x) x.begin(),x.end()
  14. #define sz(x) ((int)(x).size())
  15. #define test ll _x86_; cin>>_x86_; while(_x86_--)
  16.  
  17. void solve()
  18. {
  19. int n, k, baseh{0}; cin>>n>>k;
  20. vector<pair<int,int>> m(n); vi h(n);
  21.  
  22. f(i,0,n-1) cin>>m[i].first;
  23. f(i,0,n-1) cin>>m[i].second;
  24.  
  25. sort(all(m));
  26.  
  27. f(i, 0, n-1) h[i] = m[i].first;
  28.  
  29. fr(i, n-2, 0) m[i].second = min(m[i+1].second, m[i].second);
  30.  
  31. while(k > 0)
  32. {
  33. int ded = upper_bound(all(h), k+baseh) - h.begin();
  34.  
  35. if(ded == n) { yes; return; }
  36.  
  37. baseh += k;
  38. k -= m[ded].second;
  39. }
  40. no;
  41. }
  42.  
  43. int32_t main()
  44. {
  45. speed; test
  46.  
  47. solve();
  48. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement