Cod sursa(job #2809931)

Utilizator Victor2006Nicola Victor-Teodor Victor2006 Data 27 noiembrie 2021 22:12:05
Problema Lupul Urias si Rau Scor 8
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <stdio.h>
#include <iostream>
#define N 100000

struct node {
    int dis;
    int cost;
};

bool operator > ( const node& a, const node& b ) {
    if ( a.cost == b.cost )
        return (a.dis < b.dis);
    return (a.cost > b.cost);
}

bool operator < ( const node& a, const node& b ) {
    return !(a.cost > b.cost);
}

node heap[N];
int nheap;

int parent( int nod ) { return (nod - 1) / 2; }
int leftChild( int nod ) { return nod * 2 + 1; }
int rightChild( int nod ) { return nod * 2 + 2; }

void upHeap( int nod ) {
    while ( nod && heap[parent( nod )] < heap[nod] ) {
        std::swap( heap[parent( nod )], heap[nod] );
        nod = parent( nod );
    }
}

void downHeap( int nod ) {
    int maxx = nod;
    if ( leftChild( nod ) < nheap && heap[leftChild( nod )] > heap[maxx] )
        maxx = leftChild( nod );
    if ( rightChild( nod ) < nheap && heap[rightChild( nod )] > heap[maxx] )
        maxx = rightChild( nod );
    if ( nod != maxx ) {
        std::swap( heap[maxx], heap[nod] );
        downHeap( maxx );
    }
}

void addToHeap( node val ) {
    heap[nheap] = val;
    upHeap( nheap );
    nheap ++;
}

node removeMin() {
    node aux = heap[0];
    heap[0] = heap[-- nheap];
    downHeap( 0 );
    return aux;
}

node getMin() { return heap[0]; }
bool isHeapEmpty() { return (nheap == 0); }

/*void afis( int nod ) {
    if ( nod >= nheap )
        return;
    printf( "%d %d\n", heap[nod].dis, heap[nod].cost );
    afis( leftChild( nod ) );
    afis( rightChild( nod ) );
}*/

int main() {
    FILE *fin, *fout;
    int n, range, pas, ans, addDis;
    node x;

    fin = fopen( "lupu.in", "r" );
    fscanf( fin, "%d%d%d", &n, &range, &pas );
    for ( int i = 0; i < n; i ++ ) {
        fscanf( fin, "%d%d", &x.dis, &x.cost );
        addToHeap( x );
    }
    fclose( fin );

    //afis( 0 );

    ans = addDis = 0;
    while ( !isHeapEmpty() > 0 ) {
        while ( !isHeapEmpty() && getMin().dis + addDis > range )
            removeMin();
        if ( !isHeapEmpty() )
            ans += removeMin().cost;
        addDis += pas;
    }

    fout = fopen( "lupu.out", "w" );
    fprintf( fout, "%d\n", ans );
    fclose( fout );
    return 0;
}