Cod sursa(job #1435482)

Utilizator TPotecTiberiu Potec TPotec Data 13 mai 2015 16:03:05
Problema Lupul Urias si Rau Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <fstream>
#include <algorithm>
using namespace std;

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

int n,x,l,distanta,nrlana,h[100001],nh=0;

struct oaie
{
    int distanta;
    int lana;
};

oaie v[1001];

void Read()
{
    in>>n>>x>>l;
    for(int i=1; i<=n; i++)
    {
        in>>v[i].distanta;
        in>>v[i].lana;
    }
}

int compare(oaie i, oaie j)
{
    return (i.distanta>j.distanta);
}

void schimb(int p, int q)
{
    int aux=h[p];
    h[p]=h[q];
    h[q]=aux;
}

void urca(int p)
{
    while(p>1 && h[p]<h[p/2])
    {
        schimb(p,p/2);
        p/=2;
    }
}

void coboara(int p)
{
    int fs=2*p,fd=2*p+1,bun=p;
    if(fs<=nh && h[fs]<h[bun])
        bun=fs;
    if(fd<=nh && h[fd]<h[bun])
        bun=fd;
    if(bun!=p)
    {
        schimb(p,bun);
        coboara(bun);
    }
}

int main()
{
    Read();
    int i,j,nh=0,scor=0;
    sort(v+1,v+n+1,compare);
    int t=0;
    for(int i=1; i<=n; i++)
    {
        if(v[i].distanta+t*l<=x)
        {
            h[++nh]=v[i].lana;
            urca(nh);
            t++;
            scor+=v[i].lana;
        }
        else
        {
            if(v[i].lana>h[1])
            {
                scor+=v[i].lana-h[1];
                h[1]=v[i].lana;
                coboara(1);
            }
        }
    }
    out<<scor;
    return 0;
}