View Code of Problem 1093

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct s{
    __int64 val, cost;
    s(){}
    s(__int64 tt, __int64 dd):val(tt), cost(dd){}
    bool operator < (const s &a) const{
        return cost > a.cost;
    }
}pp[100100];
bool cmp(s a, s b){
    return a.val < b.val;
}
__int64 n, m, lim;
priority_queue<s>que;
bool judge(__int64 xx, __int64 yy){
    int i;
    while(!que.empty())
        que.pop();
    for(i = 1; i <= m; i++)
        que.push(s(pp[i].val, pp[i].cost));
    int cont1, cont2, cont3;
    cont1 = cont2 = cont3 = 0;
    __int64 sum = 0;
    while(!que.empty()){
        s temp = que.top();
        que.pop();
        if(temp.val < xx && cont1 < n/2){
            cont1++;
            sum += temp.cost;
        }
        else if(temp.val == xx){
            cont2++;
            sum += temp.cost;
        }
        else if(temp.val > xx && cont3 < n/2){
            cont3++;
            sum += temp.cost;
        }
        if(sum > lim)
            return false;
        if(cont1+cont2+cont3 == n)
            return true;
    }
    return false;
}
int main(){
    int i;
    while(scanf("%I64d%I64d%I64d", &n, &m, &lim) == 3){
        while(!que.empty()) que.pop();
        for(i = 1; i <= m; i++)
            scanf("%I64d%I64d", &pp[i].val, &pp[i].cost);
        sort(pp+1, pp+1+m, cmp);
        int l = n/2+1;
        int r = m - n/2;
        __int64 res = -1;
        while(l <= r){
            int mid = (l+r) / 2;
            if(judge(pp[mid].val, pp[mid].cost)){
                res = pp[mid].val;
                l = mid + 1;
            }
            else
                r = mid - 1;
        }
        printf("%I64d\n", res);
    }
    return 0;
}