Advertisement
Josif_tepe

Untitled

Jan 9th, 2022
1,008
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.19 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. int main()
  7. {
  8.     long long a,b;
  9.     cin>>a>>b;
  10.     vector<pair<long long,long long>>v;
  11.     long long x,y;
  12.     for(long long i=0;i<a;i++)
  13.     {
  14.         cin>>x>>y;
  15.         v.push_back({x,y});
  16.     }
  17.     sort(v.begin(),v.end());
  18.     long long z[a];
  19.     long long zbir=0;
  20.     for(long long i=0;i<a;i++)
  21.     {
  22.         zbir+=v[i].second;
  23.         z[i]=zbir;
  24.     }
  25.     long long l,r,mid;
  26.     long long maxvalue=0;
  27.     for(long long i=0;i<a;i++)
  28.     {
  29.         l=i;
  30.         r=a-1;
  31.         mid=(l+r)/2;
  32.         long long najgolem=-1;
  33.         while(l<=r)
  34.         {
  35.             mid=(l+r)/2;
  36.             if(v[mid].first-v[i].first>=b)
  37.             {
  38.                 r=mid-1;
  39.             }
  40.             else
  41.             {
  42.                 najgolem=mid;
  43.                 l=mid+1;
  44.             }
  45.         }
  46.         if(najgolem + 1 < a && v[najgolem+1].first-v[i].first<b)
  47.         {
  48.             najgolem++;
  49.         }
  50.         if(i>0)
  51.         maxvalue=max(maxvalue, (z[najgolem]-z[i-1]));
  52.         else if(i==0)
  53.         maxvalue=max(maxvalue, z[najgolem]);
  54.     }
  55.     cout<<maxvalue<<endl;
  56.     return 0;
  57. }
  58.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement