#include<bits/stdc++.h> using namespace std; inline int read() { int x=0;char c=getchar(); for(;!isdigit(c);c=getchar()); for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x; } int v,n,m; long long ans=0; long long sum[100005][2]; priority_queue<long long> q; struct node { long long a; long long b; }p[100005]; inline bool cmp(node x,node y) { return x.a<y.a; } int main() { v=read();n=read();m=read(); for(int i=1;i<=n;i++) { p[i].a=read();p[i].b=read(); } sort(p+1,p+n+1,cmp); if(m&1) { for(int i=1;i<=n;i++) { sum[i][0]=sum[i-1][0]+p[i].a; q.push(p[i].a); if(q.size()>m/2) { sum[i][0]-=q.top(); q.pop(); } } while(!q.empty()) q.pop(); for(int i=n;i>=1;i--) { sum[i][1]=sum[i+1][0]+p[i].a; q.push(p[i].a); if(q.size()>m/2) { sum[i][1]-=q.top(); q.pop(); } } for(int i=m/2+1;i<=n-m/2-1;i++) { if(sum[i-1][0]+p[i].b+sum[i+1][0]<=v) ans=p[i].a; } printf("%lld\n",ans); } else { for(int i=1;i<=n;i++) { sum[i][0]=sum[i-1][0]+p[i].a; q.push(p[i].a); if(q.size()>m/2-1) { sum[i][0]-=q.top(); q.pop(); } } while(!q.empty()) q.pop(); for(int i=n;i>=1;i--) { sum[i][1]=sum[i+1][0]+p[i].a; q.push(p[i].a); if(q.size()>m/2-1) { sum[i][1]-=q.top(); q.pop(); } } for(int i=m/2;i<=n-m/2;i++) //枚举左中位数 { int le=i+1;int ri=n-m/2+1; while(le<=ri) { int mid=le+ri>>1; if(sum[i-1][0]+p[i].b+p[mid].b+sum[mid+1][1]<=v) { ans=max(ans,p[i].a+p[mid].a>>1); le=mid+1; } else ri=mid-1; } } printf("%lld\n",ans); } return 0; }
全部评论
(0) 回帖