Cod sursa(job #2043620)

Utilizator AndreidgDragomir Andrei Valentin Andreidg Data 20 octombrie 2017 12:17:20
Problema Lupul Urias si Rau Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 100005;
ifstream f("lupu.in");
ofstream g("lupu.out");

struct car
{
    int lana;
    int d;
}oi[N];

int n,x,l,nh;
int sum = 0;
int pl[N];
int h[N];
void afisare()
{
    for(int i = 1; i<= nh;i++)
    {
        g<<h[i]<<" ";
    }
    g<<"\n\n";
}
void urc()
{
    int poz = nh;
    //g<<nh<<"\n";
    while(poz > 1 && h[poz] > h[poz/2])
    {
        swap(h[poz],h[poz/2]);
        poz = poz / 2;
    }
    //afisare();
}
void coboara()
{
    //g<<h[1]<<" ";
    if(nh >0)
    {
        sum += h[1];
        h[1] = h[nh];
        nh--;
    }
    else
        return;

    int poz = 1;

    while(2*poz <= nh)
    {
        int pmediu = poz;
        if(h[poz]<h[2*poz])
        {
            pmediu = 2 * poz;
        }
        if(2*poz+1<=nh && h[pmediu] < h[2*poz+1])
        {
            pmediu = 2 * poz +1;
        }
        if(pmediu != poz)
        {
            swap(h[pmediu],h[poz]);
            poz = pmediu;
        }
        else
        {
            break;
        }
    }
}
bool cmp(car a, car b)
{

    return a.d>b.d;
}
int main()
{
    f>>n>>x>>l;
    nh = 0 ;

    for(int i = 1;i <= n; i++)
    {
        int t = 0;
        f>>oi[i].d>>oi[i].lana;
        t = (x-oi[i].d) / l;
        if(oi[i].d>x)
            t = -1;
        oi[i].d = t;
        //g<<oi[i].d<<"\n";
    }

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

    for(int i = 1; i<= n; i++)
    {
        //g<<oi[i].d<<" "<<oi[i].lana<<"\n";
    }
    int ct = 1;
    for(int i = x/l;i >= 0; i--)
    {

        while(ct<= n && i == oi[ct].d)
        {
            nh++;
            h[nh] = oi[ct].lana;
            urc();
            ct++;
        }
        coboara();
    }
    //coboara();
    g<<sum;
    f.close();
    g.close();
    return 0;
}