fork download
copy 
  1. //Believe in yourself ,( try and try and then try ), You can do it 
  2. //You don't have to be great to start but you have to start to be great 
  3. #include <iostream>
  4. #include<algorithm>
  5. #include<cmath>
  6. #include<string>
  7. #include<vector>
  8. #include <utility>
  9. #include <stack>
  10. #include <set>
  11. #include <map>
  12. #include<queue>
  13. #include<set>
  14. // 2D vector vector<vector<int>>v(n,vector<int>(m));
  15. // sort and reverse in vector sort(v.begin(), v.end(), greater<int>());
  16. // str.erase(pos,len); erase in string
  17. // a = s.substr(0, i)<<before i, b = s.substr(i)<<from i to end;
  18. // cout << (v[0] == 1 ? "YES" : "NO") << endl;
  19. // unsigned long long int
  20. // priority_queue<ll, vector<ll>, greater<ll>> p;
  21. using namespace std;
  22. #define ll long long
  23. #define all(c)  c.begin(),c.end()
  24.  
  25.  
  26. ll gcd(ll a, ll b)
  27. {
  28.     while (b != 0)
  29.     {
  30.         ll a2 = a;
  31.         a = b;        b = a2 % b;
  32.     }
  33.     return  a;
  34. }
  35.  
  36. ll lcm(ll a, ll b)
  37. {
  38.     return a / gcd(a, b) * b;
  39. }
  40.  
  41. void soso()
  42. {
  43.     ios::sync_with_stdio(0);
  44.     cin.tie(NULL);
  45.     cout.tie(NULL);
  46. }
  47. ll n, d; pair<ll,ll>arr[200005];
  48.  
  49. ll can(ll mid)
  50. {
  51.     ll sum = 0, ma = 0;
  52.     for (int i = 1; i <= n; i++)
  53.     {
  54.         if (arr[(mid - 1) + i].first - arr[i].first < d)
  55.         {
  56.             sum = arr[(mid - 1) + i].second - arr[i - 1].second;
  57.             ma = max(sum, ma);
  58.         }
  59.     }
  60.     return ma;
  61. }
  62. int main()
  63. {
  64.     soso();
  65.     cin >> n >> d;
  66.     for (int i = 1; i <= n; i++)cin >> arr[i].first >> arr[i].second;
  67.     sort(arr, arr + n+1);
  68.     for (int i = 1; i <= n; i++)arr[i].second += arr[i - 1].second;
  69.  
  70.     ll l = 1, r = n, ans = 0;
  71.  
  72.     while (l <= r)
  73.     {
  74.         ll mid = (l + r) / 2;
  75.         cout << mid << "\n";
  76.         ll f = can(mid);
  77.         if (can(mid))
  78.         {
  79.             l = mid + 1;
  80.             ans = max(f, ans);
  81.         }
  82.         else
  83.             r = mid - 1;
  84.  
  85.     }
  86.     cout << ans;
  87. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/8wcdsm
language:
C++ (gcc 8.3)
created:
16 days 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!