Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
[POJ] 2431 – Expedition - http://kuoe0.ch/1512/poj-2431-expedition/
/*
* =====================================================================================
*
* Filename: 2431 - Expedition.cpp
*
* Description: http://poj.org/problem?id=2431
*
* Version: 1.0
* Created: 2012/02/08 18時46分09秒
* Revision: none
* Compiler: gcc
*
* Author: KuoE0 (tommy790506@hotmail.com)
* Organization: NCKU CSIE WMMKS Lab, Taiwan
*
* =====================================================================================
*/
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
int n;
pair< int, int > stop[ 10010 ];
int P, L;
int main() {
while ( ~scanf( "%d", &n ) ) {
int d, c;
priority_queue< int > PQ;
for ( int i = 0; i < n; ++i ) {
scanf( "%d %d", &d, &c );
stop[ i ] = pair< int, int >( d, c );
}
scanf( "%d %d", &d, &c );
for ( int i = 0; i < n; ++i )
stop[ i ].first = d - stop[ i ].first;
int cnt = 0, MAX = 0;
sort( stop, stop + n );
stop[ n ] = pair< int, int >( d, 0 );
for ( int i = 0; i < n + 1; ++i ) {
while ( c < stop[ i ].first && !PQ.empty() ) {
c += PQ.top(), PQ.pop();
++cnt;
}
if ( c < stop[ i ].first )
break;
PQ.push( stop[ i ].second );
}
if ( c < d )
cnt = -1;
printf( "%d\n", cnt );
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.