Cod sursa(job #1833285)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 22 decembrie 2016 00:33:07
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL n,x,l,d,a,timp,maxt;
LL sol;
pair<LL,LL> v[100005];
bool cmp(pair<LL,LL> a,pair<LL,LL> b)
{
    if(a.first>b.first) return 1;
    return 0;
}
typedef struct tip
{
    LL oaie;
};
bool operator<(const tip& a,const tip& b)
{
    return v[a.oaie].second<v[b.oaie].second;
}
priority_queue<tip> q;
int main()
{
    freopen("lupu.in","r",stdin);
    freopen("lupu.out","w",stdout);
    scanf("%lld%lld%lld",&n,&x,&l);
    for(LL i=1LL;i<=n;i++)
    {
        scanf("%lld%lld",&d,&a);
        timp=1LL+((x-d)/l);
        v[i]=make_pair(timp,a);
    }
    sort(v+1,v+n+1,cmp);
    while(n>0 && v[n].first<=0) n--;
    maxt=v[1].first;
    LL x=1;
    for(LL i=maxt;i>=1LL;i--)
    {
        while(x<=n && v[x].first>=i)
        {
            q.push({x});
            x++;
        }
        if(!q.empty())
        {
        sol=sol+1LL*v[q.top().oaie].second;
        q.pop();
        }
    }
    printf("%lld\n",sol);
    return 0;
}