fork download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define bit(mask,i) ((mask>>i)&1)
  5. #define all(x) (x).begin(),(x).end()
  6. #define pb push_back
  7. #define enl '\n'
  8. #define fi first
  9. #define se second
  10. #define FOR0(i,b) for(int i=(0),_b=(b);i<_b;i++)
  11. #define FOR(i, a, b) for(int i=(a),_b=(b);i<=_b;i++)
  12. #define FOD(i, a, b) for(int i=(a),_b=(b);i>=_b;i--)
  13.  
  14. using ull = unsigned long long;
  15. using ll = long long;
  16. using ii = pair<int, int>;
  17. using iii = pair<ii, int>;
  18. using vi = vector<int>;
  19. using vvi = vector<vector<int>>;
  20. using vii = vector<ii>;
  21.  
  22. mt19937 Rd(time(0));
  23. ll Rand(ll l,ll r){
  24. return l+Rd()%(r-l+1);
  25. }
  26.  
  27. mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
  28.  
  29. const int maxN = 1e6, cc = 500, N = 1e6+5, MOD = 1e9 + 7, base = 31;
  30. const ll oo = 1e18;
  31.  
  32. struct Point{
  33. ll x, val;
  34. Point(ll _x = 0, ll _val = 0) : val(_val), x(_x){}
  35. bool operator < (const Point &b) const {
  36. return val < b.val;
  37. }
  38. };
  39.  
  40. int n;
  41.  
  42. ll d, b, cnt[111], t[N];
  43.  
  44. Point a[N];
  45.  
  46. vi compress;
  47.  
  48. vector<Point> Slef, Srig;
  49.  
  50. void inp(){
  51. cin >> n >> d >> b;
  52. FOR0(i, n) cin >> a[i].x >> a[i].val, compress.pb(d - a[i].x), compress.pb(a[i].x);
  53. }
  54.  
  55. void solve(){
  56. sort(all(compress));
  57. compress.erase(unique(all(compress)), compress.end());
  58. sort(a, a + n,[](Point c, Point d){
  59. return c.x < d.x;
  60. });
  61. // cout << enl;
  62. //// FOR0(i, n) cout << a[i].x << ' ' << a[i].val << enl;
  63. // cout << enl;
  64. int lef = n / 2, rig = n - lef;
  65. ll res = 0;
  66. for(int mask = 1; mask < (1 << lef); mask++){
  67. ll sum = 0;
  68. ll mnx = oo, mxx = -oo;
  69. FOR0(i, lef){
  70. if(bit(mask, i)){
  71. sum += a[i].val;
  72. mnx = min(mnx, a[i].x);
  73. mxx = max(mxx, a[i].x);
  74. }
  75. }
  76. if(mxx - mnx <= d && sum <= b) res++;
  77. if(sum <= b){
  78. Slef.pb({mnx, sum});
  79. int id = lower_bound(all(compress), mnx) - compress.begin() + 1;
  80. cnt[id]++;
  81. }
  82. }
  83.  
  84. for(int mask = 1; mask < (1 << rig); mask++){
  85. ll sum = 0;
  86. ll mnx = oo, mxx = -oo;
  87. FOR0(i, rig){
  88. if(bit(mask, i)){
  89. sum += a[i + lef].val;
  90. mnx = min(mnx, a[i + lef].x);
  91. mxx = max(mxx, a[i + lef].x);
  92. }
  93. }
  94. if(mxx - mnx <= d && sum <= b) res++;
  95. if(sum <= b) Srig.pb({mxx, sum});
  96. }
  97.  
  98. sort(all(Slef), [](const Point &c, const Point &d){
  99. return c.val > d.val;
  100. });
  101. sort(all(Srig));
  102. int pos = 0;
  103. // for(auto[m, sum] : Slef) cout << m << ' ' << sum << enl;
  104. // cout << enl;
  105. // for(auto[m, sum] : Srig) cout << m << ' ' << sum << enl;
  106. // cout << res << enl;
  107. for(auto[mxx, sum] : Srig){
  108. while(pos < Slef.size() && Slef[pos].val + sum > b){
  109. int idx = lower_bound(all(compress), Slef[pos].x) - compress.begin() + 1;
  110. cnt[idx]--;
  111. pos++;
  112. }
  113. int id = lower_bound(all(compress), mxx - d) - compress.begin() + 1;
  114. FOR(i, id, (int)compress.size()) res += cnt[i];
  115. // cout << res << enl;
  116. }
  117. cout << res << enl;
  118. }
  119.  
  120. int main(){
  121. //freopen("name.inp","r",stdin);
  122. //freopen("name.out","w",stdout);
  123. ios::sync_with_stdio(false);
  124. cin.tie(NULL);
  125. cout.tie(NULL);
  126. inp();
  127. solve();
  128. }
  129.  
Success #stdin #stdout 0.01s 17996KB
stdin
Standard input is empty
stdout
0