# 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;
}

```
This entry was posted in poj. Bookmark the permalink.