Cod sursa(job #1058567)

Utilizator rebound212Mihnea Savu rebound212 Data 15 decembrie 2013 17:54:06
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<cstdio>
#include<vector>
#include<set>
#include<algorithm>
 
using namespace std;
 
vector <pair<int,int> > v;
multiset<int> h;
long long n,k,l,i,mx,d,PUF,s;
 
bool cmp(pair<int,int> a, pair<int,int> b)
{
    if (a.second >b.second) return 1;
    return 0;
}
 
int main()
{
    freopen("lupu.in","r",stdin);
    freopen("lupu.out","w",stdout);
    scanf("%lld%lld%lld",&n,&k,&l);
    mx=0;
    s=0;
    for(i=1;i<=n;i++)
    {
        scanf("%lld%lld",&d,&PUF);
        v.push_back(make_pair(PUF,(k-d)/l+1));
        if((k-d)/l>=mx)
        {
            mx=(k-d)/l;
            mx++;
        }
    }
    vector <pair<int,int> > ::iterator it;
    sort(v.begin(),v.end(),cmp);
    multiset<int> ::iterator it2;
    it=v.begin();
    while(mx>0)
    {
        while(it!=v.end()&&(*it).second==mx)
        {
            h.insert((*it).first);
            it++;
        }
        if(!h.empty())
        {
            it2=h.end();
            it2--;
            s+=*it2;
            h.erase(it2);
        }
        mx--;
    }
    printf("%lld\n",s);
}