Cod sursa(job #1435483)

Utilizator MateiTMatei Tita MateiT Data 13 mai 2015 16:13:59
Problema Lupul Urias si Rau Scor 12
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream in("lupu.in");
ofstream out("lupu.out");

int n,x,d,l,h[200010];
int fs,p,nh=0,bun,scor;

struct oaie{
    int dist;
    int lana;};
oaie v[200010];

int cmp(oaie a,oaie b)
{
    return (a.dist>b.dist);
}

void schimb(int p, int q)
{
    int aux=h[p];
    h[p]=h[q];
    h[q]=aux;
}

void urca(int p)
{
    while(p>1 && h[p]<h[p/2])
    {
        schimb(p,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)
    {
        schimb(p,bun);
        coboara(bun);
    }
}

void citire()
{
    in>>n>>x>>l;
    for(int i=1;i<=n;i++)
    {
        in>>v[i].dist>>v[i].lana;
    }
}

int main()
{
     citire();
     int i,j,t;
     sort(v+1,v+n+1,cmp);
     t=0;
     scor=0;
     for(i=1;i<=n;i++)
     {
        if(v[i].dist+t*l<=x)
        {
            h[++nh]=v[i].lana;
            urca(nh);
            t++;
            scor+=v[i].lana;
        }
        else
            if(v[i].lana>h[i])
            {
                scor+=v[i].lana-h[1];
                h[1]=v[i].lana;
                coboara(1);
            }
    }
    out<<scor;
    return 0;
}