Untitled

mail@pastecode.io avatar
unknown
plain_text
19 days ago
1.8 kB
0
Indexable
Never
#pragma GCC optimize("02")
#pragma GCC target("avx,avx2,fma")
#include <iostream>
#include <algorithm>

typedef long long ll; // p + q = n; dpt khoang: p(logp + 10) + q(logq+10) = plogp + qlogq + 10n;
// +10 vi trong for while nhieu lenh; // test lon nhat: 2,7 * 10^6
using namespace std;

int ub(pair<int,int> a[], int n, int x){ // phan tu cuoi cung <= x
    int m, l = 1, r = n-1, res = 0;
    while(l <= r){
        m = (l+r)/2;
        if(x < a[m].first) r = m-1;
        else{
            res = m;
            l = m+1;
        }
    }
    return res;
}
pair<int, int> a[100001], b[100001];
// 1<=n<=10^5; |X|,|xi|<=10^6; 1<=wi<=10^9; 1<=k<=10^9
// X lam moc, a : trai, b : phai
int main() { // code hoiw trau
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int i, cs, n, X, k, p = 1, q = 1, len = 0; ll sm;
    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); // cong don
    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 res = 0;
    for(i = 0; i < p; i++){ // sang trai roi sang phai
        len = 2*a[i].first;
        cs = k-len; if(cs <= 0) break;
        sm = a[i].second + b[ub(b, q, cs)].second;
        if(res < sm) res = sm; // cap nhat
    }
    for(i = 0; i < q; i++){ // sang phai roi sang trai
        len = 2*b[i].first;
        cs = k-len; if(cs <= 0) break;
        sm = b[i].second + a[ub(a, p, cs)].second;
        if(res < sm) res = sm;  // cap nhat
    }
    cout << res << endl;
       
    return 0;
}
Leave a Comment