Poj Solution 3171

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

#include <stdio.h>
#include <algorithm>

using namespace std;
int t1[10000], t2[10000], f[10000], t[10000], fee[10000];
int id[10000];

bool cmp( int a, int b ) {
    return t2[a] < t2[b];
}

int main( ) {
    int i, n, m, e, tn, x, y, k, temp;
    
    scanf( "%d%d%d", &n, &m, &e );

    for( i=0; i<n; i++ ) {
        scanf( "%d%d%d", t1+i, t2+i, f+i );
        id[i] = i;
    }

    sort( id, id+n, cmp );

    tn = 1;
    fee[0] = 0;
    t[0] = m;

    for( i=0; i<n; i++ ) {
        x = t1[ id[i] ];
        y = t2[ id[i] ];
        k = lower_bound( t, t+tn, x ) - t;

        if( k < tn ) {
            temp = f[id[i]] + fee[k];
            while( tn && temp <= fee[tn-1] )
                tn--;
            fee[tn] = temp;
            t[tn] = y+1;
            tn++;
        }
    }

    if( t[tn-1] != e+1 )
        printf( "-1n" );
    else
        printf( "%dn", fee[tn-1] );

    return 0;
}


											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *