Cod sursa(job #1515911)

Utilizator ZeBuGgErCasapu Andreas ZeBuGgEr Data 2 noiembrie 2015 13:12:12
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 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,num,pos;

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])
            {
                swap(heap[nod],heap[nod*2]);
                hrem(nod*2);
            }
        }
    }
}

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

    fscanf(fin,"%lld %lld %lld",&n,&x,&l);
    num=x/l+2;

    for(int i=1;i<=n;i++)
    {
        fscanf(fin,"%lld %lld",&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);
    pos=1;
    for(int i=num;i>0;i--)
    {
        for(;v[pos].dist==i;)
        {
            lph++;
            heap[lph]=v[pos].lana;
            hadd(lph);
            pos++;
        }
        if(lph>=1)
        {
            sum+=heap[1];
            heap[1]=heap[lph];
            lph--;
            hrem(1);
        }
    }
    fprintf(fout,"%lld",sum);
}