Cod sursa(job #1624755)

Utilizator andi12Draghici Andrei andi12 Data 2 martie 2016 13:26:32
Problema Lupul Urias si Rau Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <cstdio>
#include<algorithm>
using namespace std;
struct oaie
{
    int dist;
    int lana;
};
int cmp(oaie x,oaie y)
{
    if(x.dist<=y.dist)
        return 0;
    else
        return 1;
}
const int N=100005;
oaie v[N];
int h[N],lst[N];
int nrh;
void schimba(int poz1,int poz2)
{
    int aux=h[poz1];
    h[poz1]=h[poz2];
    h[poz2]=aux;
}
void coboara(int poz)
{
    int fs=2*poz,fd=2*poz+1,bun=poz;
    if(fs<=nrh && h[bun]>h[fs])
        bun=fs;
    if(fd<=nrh && h[bun]>h[fd])
        bun=fd;
    if(bun!=poz)
    {
        schimba(poz,bun);
        coboara(bun);
    }
}
void urca(int poz)
{
    if(poz/2>0 && h[poz]<h[poz/2])
    {
        schimba(poz,poz/2);
        urca(poz/2);
    }
}
void ad(int val)
{
    nrh++;
    h[nrh]=val;
    urca(nrh);
}
void del()
{
    h[1]=h[nrh];
    nrh--;
    coboara(1);
}
int main()
{
    FILE *in,*out;
    in=fopen("lupu.in","r");
    out=fopen("lupu.out","w");
    int n,x,l,i,timp=0,s=0;
    fscanf(in,"%d%d%d",&n,&x,&l);
    for(i=1;i<=n;i++)
        fscanf(in,"%d%d",&v[i].dist,&v[i].lana);
    sort(v+1,v+n+1,cmp);
    for(i=1;i<=n;i++)
    {
        if(v[i].dist+timp<=x)
        {
            ad(v[i].lana);
            timp=timp+l;
        }
        else
        {
            if(v[i].lana>h[1])
            {
                del();
                ad(v[i].lana);
            }
        }
    }
    for(i=1;i<=nrh;i++)
        s=s+h[i];
    fprintf(out,"%d",s);
    return 0;
}