Untitled

 avatar
unknown
plain_text
10 months ago
1.9 kB
7
Indexable
#pragma GCC optimize("02")
#pragma GCC target("avx,avx2,fma")
#include <iostream>
#include <algorithm>

typedef long long ll;

using namespace std;

int ub(pair<int,int> a[], int n, int x){ //upper_bound
    int m, l = 0, r = n-1, res = n-1;
    while(l <= r){
        m = (l+r)/2;
        if(a[m].first <= x) l = m+1;
        else{
            if(res > m) res = m;
            r = m-1;
        }
    }
    return res;
}
pair<int, int> a[100001], b[100001];

int main() { // code hoiw trau
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int i, j, cs, sm, n, X, k, p = 1, q = 1, len = 0; cin >> n >> X >> k;
    a[0] = b[0] = {0, 0};
    for(i = 0; i < n; i++){
        cin >> cs >> sm;
        if(cs < X) a[p++] = {X-cs, sm};
        else b[q++] = {cs-X, sm};
    }
    sort(a+1, a+p); sort(b+1, b+q);
    for(i = 1; i < p; i++)
        a[i].second += a[i-1].second;
    for(i = 1; i < q; i++)
        b[i].second += b[i-1].second;
    
    ll sum = 0, res = 0;
    for(i = 0; i <= p; i++){
        if((a[i].first <= k) && (i != p)) continue;
        i -= 1;
        if(res < a[i].second)
            res = a[i].second;
        break;
    }
    for(i = 0; i <= q; i++){
        if((b[i].first <= k) && (i != q)) continue;
        i -= 1;
        if(res < b[i].second)
            res = b[i].second;
        break;
    }
    for(i = 0; i < p; i++){
        len = 2*a[i].first;
        if(k-len <= 0) break;
        sum = a[i].second;
        j = ub(b, q, k-len);
        if(j!=0) sum += b[j-1].second;
        if(res < sum) res = sum;
    }
    for(i = 0; i < q; i++){
        len = 2*b[i].first;
        if(k-len <= 0) break;
        sum = b[i].second;
        j = ub(a, p, k-len);
        if(j!=0) sum += a[j-1].second;
        if(res < sum) res = sum;
    }
    cout << res << endl;
       
    return 0;
}
Editor is loading...
Leave a Comment