Cod sursa(job #922534)

Utilizator dariusdariusMarian Darius dariusdarius Data 22 martie 2013 12:57:27
Problema Lupul Urias si Rau Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
vector<int> v[100005];
struct Str
{
    int c,d;
} a[100005];
class cmp
{
public: inline bool operator()(const Str &a,const Str &b)
    {
        return a.c<b.c;
    }
};
priority_queue<Str, vector<Str>, cmp> q;
int main()
{
    freopen("lupu.in","r",stdin);
    freopen("lupu.out","w",stdout);
    int n,i,x,l;
    scanf("%d%d%d",&n,&x,&l);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i].d,&a[i].c);
        ///a[i].t = ziua maxima in care poate fi luata i:
        if(a[i].d<=x)
            v[((x-a[i].d)/l+1)>n?n:((x-a[i].d)/l+1)].push_back(i);
    }
    int ans=0;
    for(int t=n;t>=1;t--)
    {
        for(int i=0;i<(int)v[t].size();i++)
            q.push(a[v[t][i]]);
        if(!q.empty())
            ans+=q.top().c,
            q.pop();
    }
    printf("%d\n",ans);
    return 0;
}