View Code of Problem 1093

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 111111;

pair<int, int> cow[maxn];
int lower[maxn], upper[maxn];

int main() {
    int n, c, f;
    while(~scanf("%d%d%d", &n, &c, &f)) {
        memset(lower, -1, sizeof(lower));
        memset(upper, -1, sizeof(upper));
        for(int i = 0; i < c; i++)
            scanf("%d%d", &cow[i].first, &cow[i].second);
        sort(cow, cow+c);
        int half = n/2;
        int tot = 0;
        priority_queue<int> pq;
        for(int i = 0; i < c; i++) {
            lower[i] = pq.size() == half ? tot : 1 << 30;
            pq.push(cow[i].second);
            tot += cow[i].second;
            if(pq.size() > half) {  //去掉经费最多的
                tot -= pq.top();
                pq.pop();
            }
        }
        tot = 0;
        while(!pq.empty()) {pq.pop();}
        for(int i = c-1; i >= 0; i--) {
            upper[i] = pq.size() == half ? tot : 1 << 30;
            pq.push(cow[i].second);
            tot += cow[i].second;
            if(pq.size() > half) {  //去掉经费最多的
                tot -= pq.top();
                pq.pop();
            }
        }
        int ans = -1;
        for(int i = c-1; i >= 0; i--) {
            if(lower[i] + cow[i].second + upper[i] <= f) {
                ans = cow[i].first;
                break;
            }
        }
        printf("%d\n", ans);
        while(!pq.empty()) {pq.pop();}
    }
    return 0;
}