Cod sursa(job #1027026)

Utilizator PavelPavel Ana-Oriana Pavel Data 12 noiembrie 2013 13:01:33
Problema Lupul Urias si Rau Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <cstdio>
#include <algorithm>
using namespace std;

FILE *in ,*out;

struct lupul
{
    int dt,lana;
};
const int N = 100004;
lupul v[N];
int h[N],hn;

bool cmp (lupul x , lupul y)
{
    if(x.dt > y.dt)
        return 0;
    return 1;
}

inline void schimb (int x,int y)
{
    int aux = h[x];
    h[x] = h[y];
    h[y] = aux;
}

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

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

    if(fd<=hn && h[fd]<h[bun]) bun=fd;

    if(bun!=i)
    {
        schimb(bun,i);
        coboara(bun);
    }
}

int main()
{
    in = fopen("lupu.in","r");
    out = fopen("lupu.out","w");
    int i,n,x,l;
    fscanf(in,"%d%d%d",&n,&x,&l);
    for(int i = 1 ; i<=n ; i++){
        fscanf(in,"%d%d",&v[i].dt,&v[i].lana);
        if(v[i].dt > x)
            v[i].dt = 0;
        else
            v[i].dt = (x-v[i].dt)/l+1;
    }
    hn=0;
    sort(v+1,v+n+1,cmp);
    int d = 0;
    for(i=1 ; i<=n ; i++)
    {
        d = v[i].dt-v[i-1].dt;
        if(d > 0)
        {
            h[++hn]=v[i].lana;
            urca(hn);
            //d--;
        }
        else
            if(hn>0 && h[1]<v[i].lana)
            {
                h[1]=v[i].lana;
                coboara(1);

            }
    }
    long long rez=0;
    for(int i = 1 ; i <= hn ; i++)
        rez+=h[i];
    fprintf(out,"%lld\n",rez);
    return 0;
}