Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- long long D[100005], D2[100005];
- pair<long long, long long> v[100005];
- vector<long long> A, A2;
- long long N, X, K;
- long long solution;
- int main(){
- cin >> N>> X >> K;
- for(int i = 1; i <= N; i ++)
- {
- cin >> v[i].first >> v[i].second;
- if(v[i].first < X)
- A.push_back(abs(v[i].first - X));
- else
- A2.push_back(abs(v[i].first - X));
- }
- sort(A.begin(), A.end());
- sort(A2.begin(), A2.end());
- sort(v + 1, v + N + 1);
- for(int i = N; i >= 1; i --)
- {
- if(v[i].first < X)
- D[i] += D[i + 1] + v[i].second;
- }
- int j = 1;
- while( v[j].first < X && j <= N)
- {
- if(X - v[j].first <= K)
- {
- solution += v[j].second;
- }
- j ++;
- }
- int j2 = j;
- while( v[j2].first > X && j2 <= N)
- {
- if(v[j2].first - X <= K)
- {
- D2[j2] += v[j2].second + D2[j2 - 1];
- solution = max(solution, D2[j2]);
- }
- j2 ++;
- }
- j2 --;
- for(int i = j; i <= N; i ++)
- {
- if(v[i].first > X && v[i].first - X <= K)
- {
- auto pos = upper_bound(A.begin(), A.end(), (K - 2 * abs(v[i].first - X) ) ) - A.begin();
- if(pos > 0)
- if(pos )
- solution = max(solution, D2[i] + D[j - pos]);
- }
- }
- for(int i = 1; i < j; i ++)
- {
- if(v[i].first < X && X - v[i].first <= K)
- {
- auto pos = upper_bound(A2.begin(), A2.end(), (K - 2 * abs(v[i].first - X) ) ) - A2.begin();
- if(pos > 0)
- solution = max(solution, D[i] + D2[j + pos - 1]);
- }
- }
- cout << solution;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement