Cod sursa(job #911766)

Utilizator valentina506Moraru Valentina valentina506 Data 11 martie 2013 20:55:18
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include<fstream>
#include<set>
#include<algorithm>
using namespace std;
int n,m,k,i,elem,pas;
struct oaie
{
     int dist,l;
};
oaie a[100002];
unsigned long long int sol;
multiset<int,greater <int> > heap;
bool cmp(oaie a, oaie b)
{ return a.dist<b.dist;}
int maxim(int a,int b)
{
    if(a>b)
    return a;
    return b;
}
int main()
{
    ifstream f("lupu.in");
    ofstream g("lupu.out");
    f>>n>>m>>k;
    for(i=1;i<=n;++i)
    {
        f>>a[i].dist>>a[i].l;
        {a[i].dist=(m-a[i].dist)/k+1;
        pas=maxim(pas,a[i].dist);}
    }
    sort(a+1,a+n+1,cmp);
    elem=n;
    for(i=pas;i>0;--i)
    {
         while(elem>0&&a[elem].dist==i)
         {
            heap.insert(a[elem].l);
            --elem;
         }
         if(heap.size()>0)
         {
            sol+=*heap.begin();
            heap.erase(heap.begin());
        }
    }

    g<<sol;
}