Advertisement
Guest User

Untitled

a guest
Feb 24th, 2017
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.76 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. long long D[100005], D2[100005];
  6. pair<long long, long long> v[100005];
  7. vector<long long> A, A2;
  8. long long N, X, K;
  9. long long solution;
  10.  
  11. int main(){
  12.  
  13.     cin >> N>> X >> K;
  14.     for(int i = 1; i <= N; i ++)
  15.     {
  16.         cin >> v[i].first >> v[i].second;
  17.         if(v[i].first < X)
  18.             A.push_back(abs(v[i].first - X));
  19.         else
  20.              A2.push_back(abs(v[i].first - X));
  21.     }
  22.     sort(A.begin(), A.end());
  23.     sort(A2.begin(), A2.end());
  24.     sort(v + 1, v + N + 1);
  25.  
  26.     for(int i = N; i >= 1; i --)
  27.     {
  28.         if(v[i].first < X)
  29.         D[i] += D[i + 1] + v[i].second;
  30.     }
  31.  
  32.     int j = 1;
  33.     while( v[j].first < X && j <= N)
  34.     {
  35.         if(X - v[j].first <= K)
  36.         {
  37.             solution += v[j].second;
  38.         }
  39.         j ++;
  40.     }
  41.     int j2 = j;
  42.     while( v[j2].first > X && j2 <= N)
  43.     {
  44.         if(v[j2].first - X <= K)
  45.         {
  46.             D2[j2] += v[j2].second + D2[j2 - 1];
  47.             solution = max(solution, D2[j2]);
  48.         }
  49.         j2 ++;
  50.     }
  51.     j2 --;
  52.  
  53.     for(int i = j; i <= N; i ++)
  54.     {
  55.         if(v[i].first > X && v[i].first - X <= K)
  56.         {
  57.             auto pos = upper_bound(A.begin(), A.end(), (K - 2 * abs(v[i].first - X) ) ) - A.begin();
  58.             if(pos > 0)
  59.                 if(pos )
  60.                 solution = max(solution, D2[i] + D[j - pos]);
  61.         }
  62.     }
  63.  
  64.     for(int i = 1; i < j; i ++)
  65.     {
  66.         if(v[i].first < X && X - v[i].first <= K)
  67.         {
  68.             auto pos = upper_bound(A2.begin(), A2.end(), (K - 2 * abs(v[i].first - X) ) ) - A2.begin();
  69.             if(pos > 0)
  70.                 solution = max(solution, D[i] + D2[j + pos - 1]);
  71.         }
  72.     }
  73.  
  74.     cout << solution;
  75.  
  76.  
  77.     return 0;
  78. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement