Cod sursa(job #633687)

Utilizator gramatovici_paulGramatovici Paul gramatovici_paul Data 14 noiembrie 2011 14:58:15
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <algorithm>

using namespace std;

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

priority_queue <int> h;


struct oaie
{
  int d,k;
};


oaie a[100100];


bool cmp(oaie a, oaie b)
{
    return a.d<b.d;
}


int main()
{
    int n,x,l,i,s=0;
    in>>n>>x>>l;
    for(i=1;i<=n;++i)
        in>>a[i].d>>a[i].k;
    sort(a+1,a+n+1,cmp);
    for(i=1;i<=n;++i)
    {
        if(h.empty())
        {
            h.push(-a[i].k);
            x-=l;
            s+=a[i].k;
            continue;
        }
        if(a[i].d<=x)
        {
            h.push(-a[i].k);
            s+=a[i].k;
            x-=l;
            continue;
        }
        if(-h.top()<a[i].k)
        {
            s-=h.top();
            s+=a[i].k;
            h.pop();
            h.push(-a[i].k);
        }
    }
    out<<s;
    return 0;
}