Cod sursa(job #639129)

Utilizator gramatovici_paulGramatovici Paul gramatovici_paul Data 22 noiembrie 2011 15:43:37
Problema Lupul Urias si Rau Scor 80
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;
}