Cod sursa(job #1515884)

Utilizator ZeBuGgErCasapu Andreas ZeBuGgEr Data 2 noiembrie 2015 12:39:10
Problema Lupul Urias si Rau Scor 12
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
#include<stdio.h>
#include<algorithm>
#include<iostream>

using namespace std;

FILE *fin,*fout;
long long int n,x,l,lph,val;
long long int sum;

struct str
{
    long long int dist;
    long long int lana;
}v[100001];

int heap[100001];

int comp(str a,str b)
{
    return a.dist>b.dist;
}

void hadd(int nod)
{
    if(heap[nod/2]<heap[nod]&&nod!=1)
    {
        swap(heap[nod/2],heap[nod]);
        hadd(nod/2);
    }
}

void hrem(int nod)
{
    if(nod*2<=lph)
    {
        if(nod*2+1<=lph)
        {
            if(heap[nod*2]>heap[nod*2]+1)
            {
                if(heap[nod]<heap[nod*2])
                {
                    swap(heap[nod],heap[nod*2]);
                    hrem(nod*2);
                }
                else if(heap[nod]<heap[nod*2+1])
                {
                    swap(heap[nod],heap[nod*2+1]);
                    hrem(nod*2+1);
                }
            }
            else
            {
                if(heap[nod]<heap[nod*2+1])
                {
                    swap(heap[nod],heap[nod*2+1]);
                    hrem(nod*2+1);
                }
                else if(heap[nod]<heap[nod*2])
                {
                    swap(heap[nod],heap[nod*2]);
                    hrem(nod*2);
                }
            }
        }
        else
        {
            if(heap[nod]<heap[nod*2])
            {
                swap(heap[nod],heap[nod*2]);
                hrem(nod*2);
            }
        }
    }
}

int main()
{
    fin=fopen("lupu.in","r");
    fout=fopen("lupu.out","w");

    fscanf(fin,"%d %d %d",&n,&x,&l);

    for(int i=1;i<=n;i++)
    {
        fscanf(fin,"%d %d",&v[i].dist,&v[i].lana);
        v[i].dist=x-v[i].dist;
        v[i].dist/=l;
        v[i].dist++;
    }

    sort(v+1,v+n+1,comp);

    for(int i=1;i<=n&&v[i].dist>0;)
    {
        val=v[i].dist;
        for(;v[i].dist==val;i++)
        {
            lph++;
            heap[lph]=v[i].lana;
            hadd(lph);
        }
        if(lph>=1)
        {
            sum+=heap[1];
            heap[1]=heap[lph];
            lph--;
            hrem(1);
        }
    }
    fprintf(fout,"%lld",sum);
}