Cod sursa(job #1021758)

Utilizator alexpascadiAlexandru Pascadi alexpascadi Data 4 noiembrie 2013 10:32:30
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

struct oaie
{
    int lana;
    int zi;
};

oaie v[100001];
int h[100001],nr=0;

bool cmp(oaie x, oaie y)
{
    if(x.zi<y.zi) return 1;
    return 0;
}

void urca(int i)
{
    int aux;
    while(i>1 && h[i]<h[i/2])
    {
        aux=h[i];
        h[i]=h[i/2];
        h[i/2]=aux;
        i/=2;
    }
}

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

int main()
{
    FILE *in,*out;
    in=fopen("lupu.in","r");
    out=fopen("lupu.out","w");
    int n,x,l,i,val,dif;
    fscanf(in,"%d%d%d",&n,&x,&l);
    for(i=1;i<=n;i++)
    {
        fscanf(in,"%d%d",&val,&v[i].lana);
        if(val>x) v[i].zi=0;
        else v[i].zi=(x-val)/l +1;
    }
    sort(v+1,v+n+1,cmp);
    /*for(i=0;i<n;i++)
        fprintf(out,"%d %d\n",v[i].zi, v[i].lana);*/
    v[0].zi=0; dif=0;
    for(i=1;i<=n;i++)
    {
        dif=dif+v[i].zi-v[i-1].zi;
        if(dif>0)
        {
            h[++nr]=v[i].lana;
            urca(nr);
            dif--;
        }
        else if(nr>0 && h[1]<v[i].lana)
        {
            h[1]=v[i].lana;
            coboara(1);
        }
    }
    long long s=0;
    for(i=1;i<=nr;i++) s+=h[i];
    fprintf(out,"%lld",s);
}