Cod sursa(job #1043420)

Utilizator anca1243Popescu Anca anca1243 Data 28 noiembrie 2013 16:06:34
Problema Lupul Urias si Rau Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("lupu.in");
ofstream out("lupu.out");
const int N=100001;
struct oi
{
    int d,b;
} o[N];
int n,h[N],x,l,nh,dc;
void schimba(int p1,int p2)
{
    int aux = h[p1];
    h[p1]=h[p2];
    h[p2]=aux;
}
void urca(int p)
{
    while(p>1 && h[p]<h[p/2])
    {
        schimba(p,p/2);
        p/=2;
    }
}
void adauga(int val)
{
    h[++nh] = val;
    urca(nh);
}
bool cmd(oi a, oi y)
{
    if(a.d>y.d)
        return 1;
    return 0;
}
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(p!=bun)
    {
        schimba(p,bun);
        coboara(bun);
    }
}
void sterge(int p)
{
    schimba(p,nh--);
    urca(p);
    coboara(p);
}
int main()
{
    in>>n>>x>>l;
    for(int i=1;i<=n;i++)
    {
        in>>o[i].d>>o[i].b;
    }
    sort(o+1,o+n+1,cmd);
    int t=1;
    adauga(o[1].b);
    for(int i=2;i<=n;i++)
    {
        if(o[i].d +(t*2)>x && o[i].b>h[1])
        {
            sterge(1);
            t--;
        }
        if(o[i].d + (t*2)<=x)
        {
            adauga(o[i].b);
            t++;
        }
    }
    int s=0;
    for(int i=1;i<=nh;i++)
        s+=h[i];
    out<<s;
    return 0;
}