Cod sursa(job #1973109)

Utilizator dianamichesaRosu Diana Michesa dianamichesa Data 24 aprilie 2017 14:52:32
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("lupu.in");
ofstream g("lupu.out");
const int N=100001;
struct oaie
{
    int poz,lana;
} o[N];
int x,l,n,h[N],nh;
bool fct(oaie a,oaie b)
{
    return (a.poz > b.poz);
}

void urca(int p)
{
    while(p>1 && h[p]<h[p/2])
    {
        swap(h[p],h[p/2]);
        p/=2;
    }
}

void coboara(int p)
{
    int fs=2*p,fd=2*p+1,bun=p;
    if(fs<=nh && h[fs]<h[bun])
        bun=fs;
    if(fd<=nh && h[fd]<h[bun])
        bun=fd;
    if(bun!=p)
    {
        swap(h[p], h[bun]);
        coboara(bun);
    }
}

void adauga(int p)
{
    nh++;
    h[nh]=p;
    urca(nh);
}

void sterge(int p)
{
    swap(h[p],h[nh]);
    nh--;
    urca(p);
    coboara(p);
}

int main()
{
    f>>n>>x>>l;
    for(int i=1; i<=n; i++)
        f>>o[i].poz>>o[i].lana;
    sort(o+1,o+n+1,fct);
    int t=0;
    for(int i=1; i<=n; i++)
    {
        if(o[i].poz<=x-t*l)
        {
            adauga(o[i].lana);
            t++;
        }
        else if(nh > 0 && o[i].lana>h[1])
        {
            sterge(1);
            adauga(o[i].lana);
        }
        /*
        for(int i=1; i<=nh; i++)
        {
            g << h[i] << " ";
        }
        g<<'\n';
        */
    }
    long long s=0;
    for(int i=1; i<=nh; i++)
    {
        s+=h[i];
        //g << h[i] << "\n";
    }
    g<<s;
    return 0;
}