Cod sursa(job #2063036)

Utilizator PinkiePie1189Preoteasa Mircea-Costin PinkiePie1189 Data 11 noiembrie 2017 08:34:14
Problema Lupul Urias si Rau Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
#include<stdio.h>
#include<algorithm>
#define MAXN 100000
struct Sheep
{
    int profit;
    int turns_survived;
};
void Add(int x);
void Rmv(int nod);
void sift(int nod);
void percolate(int nod);
void swap_nodes(int nod1,int nod2);
bool cmp(Sheep,Sheep);
FILE*fin,*fout;
Sheep sheeps[MAXN+1];
int heap[MAXN+1];
int M=0;
int main()
{
    fin=fopen("lupu.in","r");
    fout=fopen("lupu.out","w");
    int N,X,L;
    fscanf(fin,"%d%d%d",&N,&X,&L);
    for(int i=1;i<=N;i++)
    {
        int initial_d,wool;
        fscanf(fin,"%d%d",&initial_d,&wool);
        sheeps[i].profit=wool;
        sheeps[i].turns_survived=(X-initial_d)/L+1;
        if(sheeps[i].turns_survived<0)
        {
            sheeps[i].turns_survived=0;
        }
    }
    std::sort(&sheeps[1],&sheeps[N+1],cmp);
    int curr=N;
    int ans=0;
    int Tmax=sheeps[N].turns_survived;
    for(int i=Tmax;i>=1;i--)
    {
        while(sheeps[curr].turns_survived==i && curr>=1)
        {
            Add(sheeps[curr].profit);
            curr--;
        }
        if(M>0)
        {
            ans+=heap[1];
            Rmv(1);
        }
    }
    fprintf(fout,"%d",ans);
    fclose(fin);
    fclose(fout);
    return 0;
}
bool cmp(Sheep a,Sheep b)
{
    if(a.turns_survived==b.turns_survived)
    {
        return a.profit>b.profit;
    }
    return a.turns_survived<b.turns_survived;
}
void Add(int x)
{
    heap[++M]=x;
    percolate(M);
}
void Rmv(int nod)
{
    swap_nodes(nod,M);
    M--;
    if(nod>1 && heap[nod]>heap[nod/2])
    {
        percolate(nod);
    }
    else
    {
        sift(nod);
    }
}
void sift(int nod)
{
    int son;
    do
    {
        son=0;
        if(2*nod+1<=M)
        {
            if(heap[2*nod]>heap[2*nod+1])
            {
                son=2*nod;
            }
            else
            {
                son=2*nod+1;
            }
        }
        else if(2*nod<=M)
        {
            son=2*nod;
        }
        if(heap[nod]>heap[son])
        {
            son=0;
        }
        if(son)
        {
            swap_nodes(nod,son);
            nod=son;
        }
    }while(son);
}
void percolate(int nod)
{
    while(nod>1 && heap[nod]>heap[nod/2])
    {
        swap_nodes(nod,nod/2);
        nod=nod/2;
    }
}
void swap_nodes(int nod1,int nod2)
{
    std::swap(heap[nod1],heap[nod2]);
}