Cod sursa(job #1185713)

Utilizator hrazvanHarsan Razvan hrazvan Data 16 mai 2014 15:29:10
Problema Lupul Urias si Rau Scor 80
Compilator c Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <stdio.h>
#define N_MAX 100000
int heap[ N_MAX + 1 ], ind = 1, dist[ N_MAX ], lan[ N_MAX ];

void qs ( int st, int dr ){
    int i = st, j = dr, piv = dist[ ( st + dr ) / 2 ], aux;
    while ( i <= j ){
        while ( dist[ i ] > piv )   i++;
        while ( dist[ j ] < piv )   j--;
        if ( i <= j ){
            aux = dist[ i ];  dist[ i ] = dist[ j ];  dist[ j ] = aux;
            aux = lan[ i ];   lan[ i ]  = lan[ j ];   lan[ j ]  = aux;
            i++;  j--;
        }
    }
    if ( st < j )   qs ( st, j );
    if ( i < dr )   qs ( i, dr );
    return ;
}

void AddToHeap ( int x ){
    int poz = ind;
    while ( poz > 1 && heap[ poz / 2 ] > x ){
        heap[ poz ] = heap[ poz / 2 ];
        poz /= 2;
    }
    heap[ poz ] = x;
    ind++;
    return ;
}

int DeleteFromHeap (){
    int rez = heap[ 1 ];
    int x = heap[ ind - 1 ], poz = 1, a, b, cpoz = poz - 1;
    ind--;
    while ( poz * 2 < ind && cpoz != poz ){
        a = poz * 2;  b = poz * 2 + 1;
        cpoz = poz;
        if ( poz * 2 + 1 < ind ){
            if ( heap[ a ] < heap[ b ] ){
                if ( heap[ a ] < x ){
                    heap[ poz ] = heap[ a ];
                    poz = a;
                }
            }
            else{
                if ( heap[ b ] < x ){
                    heap[ poz ] = heap[ b ];
                    poz = b;
                }
            }
        }
        else{
            if ( heap[ a ] < x ){
                heap[ poz ] = heap[ a ];
                poz = a;
            }
        }
    }
    heap[ poz ] = x;
    return rez;
}

int main()
{
    FILE *in = fopen ( "lupu.in", "r" );
    int n, x, l;
    fscanf ( in, "%d%d%d", &n, &x, &l );
    int i;
    for ( i = 1; i <= n; i++ ){
        fscanf ( in, "%d%d", &dist[ i ], &lan[ i ] );
    }
    qs ( 1, n );
    for ( i = 1; i <= n; i++ ){
        if ( dist[ i ] + ( ind - 1 ) * l <= x )      AddToHeap ( lan[ i ] );
        else  if ( ind > 1 && dist[ i ] + ( ind - 2 ) * l <= x
                  && heap[ 1 ] < lan[ i ] ){
            DeleteFromHeap ();
            AddToHeap ( lan[ i ] );
        }
    }
    fclose ( in );
    FILE *out = fopen ( "lupu.out", "w" );
    int rez = 0;
    while ( ind > 1 )   rez += DeleteFromHeap ();
    fprintf ( out, "%d", rez );
    fclose ( out );
    return 0;
}