Cod sursa(job #2042400)

Utilizator BogdanNeghinaNeghina Bogdan BogdanNeghina Data 18 octombrie 2017 16:19:19
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("lupu.in");
ofstream cout ("lupu.out");
int n,x,l,d,nrh,h[100005];
long long s;
struct oi
{
    int c,s;
};
oi v[100005];
int cmp (oi a, oi b)
{
    if(a.s>b.s)
        return 1;
    return 0;
}
void up (int cant)
{
    nrh++;
    h[nrh]=cant;
    int poz=nrh;
    while(poz>1)
    {
        if(h[poz]>h[poz/2])
        {
            swap(h[poz],h[poz/2]);
            poz/=2;
        }
        else
            return ;
    }
}
void down ()
{
    int fiu;
    h[1]=h[nrh];
    nrh--;
    int poz=1;
    while(2*poz<=nrh)
    {
        fiu=poz;
        if(h[poz]<h[2*poz])
            fiu=2*poz;
        if(2*poz+1<=nrh && h[2*poz+1]>h[fiu])
            fiu=2*poz+1;
        if(fiu==poz)
            return ;
        else
        {
            swap(h[poz],h[fiu]);
            poz=fiu;
        }
    }
}
int main ()
{
    cin>>n>>x>>l;
    for(int i=1;i<=n;i++)
    {
        cin>>d>>v[i].c;
        v[i].s=(x-d)/l+1;

    }
    sort(v+1,v+n+1,cmp);
    /*
    for(int i=1;i<=n;i++)
        cout<<v[i].c<<" "<<v[i].s<<"\n";
    */
    int j=1;
    for(int i=x/l+1;i>=1;i--)
    {
        while(j<=n && v[j].s==i)
        {
            up(v[j].c);
            j++;
        }
        if(nrh>0)
        {
           s+=h[1];
           down();
        }
    }
    cout<<s;
    return 0;
}