Cod sursa(job #1309511)

Utilizator lacraruraduRadu Matei Lacraru lacraruradu Data 5 ianuarie 2015 20:04:03
Problema Lupul Urias si Rau Scor 4
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <algorithm>
#include <fstream>

using namespace std;

ifstream in("lupu.in");
ofstream out("lupu.out");

const int nmax = 100000;
int n , nh , x , l;
int d[nmax + 1] , a[nmax + 1] , v[nmax + 1] , h[nmax + 1];

int cmp(int i1 , int i2)
{
    return (d[i1] > d[i2]);
}

void schimba(int i1 , int i2)
{
    int aux = h[i1];
    h[i1] = h[i2];
    h[i2] = aux;
}

void urca(int i)
{
    while(i >= 2 && h[i] > h[i / 2])
    {
        schimba(i / 2 , i);
        i /= 2;
    }
}

void coboara(int i)
{
    int fs = 2 * i , fd = 2 * i + 1 , bun = i;

    if(fs <= nh && h[bun] < h[fs])
        bun = fs;

    if(fd <= nh && h[bun] < h[fd])
        bun = fd;

    if(bun != i)
    {
        schimba(bun , i);
        coboara(bun);
    }
}

int main()
{
    in >> n >> x >> l;

    for(int i = 1 ; i <= n ; i++)
    {
        in >> d[i] >> a[i];
        v[i] = i;
    }

    sort(v + 1 , v + n + 1 , cmp);

    int indice = 1 , timp = 0;
    long long s = 0;
    nh = 0;

    while(indice <= n)
    {

        if(x >= timp * l + d[v[indice]])
        {
            h[++nh] = a[v[indice]];
            urca(nh);
            timp++;
        }
        else
        {
            if(h[1] < a[v[indice]])
            {
                h[nh] = a[v[indice]];
                urca(nh);
            }
        }

        indice++;
    }

    for(int i = 1 ; i <= nh ; i++)
        s += h[i];

    out << s << '\n';
    return 0;
}