Cod sursa(job #2043569)

Utilizator AndreidgDragomir Andrei Valentin Andreidg Data 20 octombrie 2017 11:08:24
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 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];
vector <int> h;
 
void urc()
{
    int poz = nh;
    while(poz > 1 && h[poz] >h[poz/2])
    {
        swap(h[poz],h[poz/2]);
        poz = poz / 2;
    }
    //g<<poz<<"\n";
}
void coboara()
{
    //int poz;
    sum += h[1];
    h[1] = h[nh];
    nh--;
    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;
        }
    }
}
bool cmp(car a, car b)
{
    if(a.d==b.d)
    {
        return a.lana > b.lana;
    }
    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((x-oi[i].d)%l!=0)
            t++;
 
        oi[i].d = t;
        //g<<oi[i].d<<"\n";
    }
    sort(oi+1,oi+n+1,cmp);
    int c = oi[1].d;
    for(int i = 1; i<= n; i++)
    {
        if(c!=oi[i].d)
        {
            coboara();
            c = oi[i].d;
        }
        nh++;
        h[nh] = oi[i].lana;
        urc();
    }
    coboara();
    g<<sum;
    f.close();
    g.close();
    return 0;
}