Cod sursa(job #2072563)

Utilizator alexburdescuBurdescu Alexandru alexburdescu Data 21 noiembrie 2017 22:39:34
Problema Lupul Urias si Rau Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
int N,X,L,S;
int heap[100099];
struct oaie
{
    int dist,lana;
} v[100099];
void urcare(int heap[], int p)
{
    while(p>=2 && heap[p]>heap[p/2])
    {
        swap(heap[p],heap[p/2]);
        p=p/2;
    }
}
void coborare(int heap[] , int nh , int p)
{
    while(2*p<=nh)
    {
        int r=2*p;
        if(r+1<=nh && heap[r]<heap[r+1])
        {
            r++;
        }
        if(heap[p]<heap[r])
        {
            swap(heap[p],heap[r]);
            p=r;
        }
        else
        {
            break;
        }
    }
}
bool fct(oaie a,oaie b)
{
    return (a.dist < b.dist);
}
int main()
{
    fin>>N>>X>>L;
    for(int i=1;i<=N;i++)
    {
        fin>>v[i].dist>>v[i].lana;
    }
    for ( int i=1;i<=N;i++)
    {
        int nivel=X/L-(X-v[i].dist)/L;
        v[i].dist=nivel;
    }
    sort(v+1,v+N+1,fct);
    int k=1 , nrel=0;
    for( int i=0;i<=X/L;i++)
    {
        for(int j=k; v[j].dist<=i;j++)
        {
            nrel++;
            heap[nrel]=v[j].lana;
            urcare(heap ,nrel);
            k=j+1;
        }
        if(nrel!=0)
        {
            S=S+heap[1];
            swap(heap[1],heap[nrel]);
            nrel--;
            coborare(heap, nrel , 1);
        }
    }
    fout<<S;
    fin.close();
    fout.close();
    return 0;
}