Untitled
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