Cod sursa(job #2499827)

Utilizator gavra_bogdanBogdan Gavra gavra_bogdan Data 26 noiembrie 2019 19:43:53
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int nmax=1e5+1005;

priority_queue <ll> pq;
pair <ll,ll> v[nmax];

bool mycmp(pair <ll,ll> a, pair <ll,ll> b)
{
    return a.first>b.first;
}

int set_pas(int i)
{
    while(v[i].first==v[i+1].first)
        {
            pq.push(v[i+1].second);
            i++;
        }
    return i+1;
}

ll get_ans(int i)
{
    int cnt=1;
    ll aux=0;
    while(cnt<=v[i-1].first-v[i].first and !pq.empty())
        {
            aux+=pq.top();
            pq.pop();
            cnt++;
        }
    return aux;
}

int main()
{
    ifstream cin("lupu.in");
    ofstream cout("lupu.out");
    ll n,k=0,x,l,ans=0,a,b;
    cin>>n>>x>>l;
    for(int i=1;i<=n;i++)
    {
        cin>>a>>b;
        if(a<=x)
            v[++k]={(x-a)/l+1,b};
    }
    sort(v+1,v+k+1,mycmp);
    int i=1;
    while(i<=k)
    {
        pq.push(v[i].second);
        i=set_pas(i);
        ans+=get_ans(i);
    }
    cout<<ans<<"\n";
    return 0;
}