Cod sursa(job #1107488)

Utilizator TodeaDariustodea darius TodeaDarius Data 13 februarie 2014 22:02:08
Problema Lupul Urias si Rau Scor 32
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
long long n,x,l,nr,t,i;
long long s;
struct oita
{
    long long x,ct;
}v[100005];
bool cmp(oita a,oita b)
{
    return(a.x<b.x);
}
void citire()
{
    scanf("%lld%lld%lld",&n,&x,&l);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&v[i].x,&v[i].ct);
}
struct comp
{
    bool operator()(const oita &a,const oita &b)
    {
        return(a.ct>b.ct);
    }
};
multiset<oita,comp>q;
long long maxim(long long a,long long b)
{
    if(b>a)
        return b;
    return a;
}
int main()
{
    freopen("lupu.in","r",stdin);
    freopen("lupu.out","w",stdout);

    citire();
    oita z;
    sort(v+1,v+n+1,cmp);
    i=1;nr=0;
    while(i<=n && v[i].x<=x)
    {
        t=(v[i].x+1)/l;
        while(i<=n && (v[i].x+1)/l==t && v[i].x<=x)
        {
            z.x=v[i].x;
            z.ct=v[i].ct;
            q.insert(z);
            i++;
        }
        if(!q.empty())
        {
            s+=(*q.begin()).ct;
            z.x=(*q.begin()).x;
            z.ct=(*q.begin()).ct;
            q.erase(q.find(z));
        }
           /* nr++;
            poz=maxim(t,poz);
            poz++;*/


    }
    long long var;
    var=v[i-1].x+l;
    while(var<=x && !q.empty())
    {
            s+=(*q.begin()).ct;
            z.x=(*q.begin()).x;
            z.ct=(*q.begin()).ct;
            q.erase(q.find(z));
            var+=l;
    }
    printf("%lld\n",s);

}