Cod sursa(job #2806337)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 22 noiembrie 2021 15:44:28
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <algorithm>
#include <stdio.h>
#include <queue>

struct Andrei{
    int d, lana;
};

bool cmp( const Andrei& A, const Andrei& B ) {
    return A.d < B.d;
}

std::priority_queue<int> heap;
Andrei v[ 100010 ];
int n, x, l;

int main()
{
    FILE *fin = fopen( "lupu.in", "r" );
    fscanf( fin, "%d%d%d", &n, &x, &l );
    for( int i = 0; i < n; i++ )
        fscanf( fin, "%d%d", &v[ i ].d, &v[ i ].lana );
    fclose( fin );

    std::sort( v, v + n, cmp );

    int poz = 0;
    long long rez = 0;
    for( int i = x / l + 1; i; i-- ) {
        while( poz < n && ( x - v[ poz ].d ) / l + 1 == i )
            heap.push( v[ poz++ ].lana );

        if( !heap.empty() ) {
            rez += heap.top();
            heap.pop();
        }
    }

    FILE *fout = fopen( "lupu.out", "w" );
    fprintf( fout, "%lld\n", rez );
    fclose( fout );
    return 0;
}