Poj Solution 2010

http://poj.org/problem?id=2010

#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

priority_queue< int ,vector<int> > q;

typedef pair< int, int > cow;

cow c[1000000];
int money[100000];
int n, m, f;

int main()
{
    int i, v;

    scanf( "%d %d %d", &n, &m, &f );
    
    for( i=0; i<m; i++ )
        scanf( "%d %d", &c[i].first, &c[i].second );

    sort( c, c+m );

    for( v=0, i=0; i<n/2; i++ )
    {
        v += c[i].second;
        q.push( c[i].second );
    }
    money[i] += v;

    for( ; i<m-n/2-1 ; i++ )
    {
        if( q.top() > c[i].second )
        {
            v -= q.top();
            q.pop();
            v += c[i].second;
            q.push( c[i].second );
        }
        money[i+1] += v;
    }

    while(!q.empty())q.pop();
    
    for( v=0,i=m-1; i>=m-n/2; i-- )
    {
        v += c[i].second;
        q.push( c[i].second );
    }
    

    for( ; i>=n/2 ;i-- )
    {
        money[i] += v;
        if( money[i] + c[i].second <= f )break;

        if( q.top() > c[i].second )
        {
            v -= q.top();
            q.pop();
            v += c[i].second;
            q.push( c[i].second );
        }
    }

    if( i>=n/2 ) printf( "%dn", c[i].first );
    else printf( "%dn", -1 );

    return 0;
}