Cod sursa(job #639369)

Utilizator vladstoickvladstoick vladstoick Data 23 noiembrie 2011 09:01:39
Problema Lupul Urias si Rau Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
priority_queue<int> q;
struct oaie
{
    int first,second;
};
int n , x , l , i , s;
oaie v[100001];
bool comp(oaie a , oaie b)
{
    if(a.first!=b.first)
        return a.first>b.first;
    return a.second>b.second;
}
int main()
{
    freopen("lupu.in","r",stdin);
    freopen("lupu.out","w",stdout);
    scanf("%d%d%d",&n,&x,&l);
    for(i=1;i<=n;i++)
        scanf("%d%d",&v[i].first,&v[i].second);
    sort(v+1,v+n+1,comp);


    //q.push(nume element)
    //q.size
    //q.top()
    //q.pop()
    int consta=0;
    for(i=1;i<=n;i++)
    {
        if(v[i].first+l*consta<=x || consta==0)
        {
            q.push(v[i].second);
            s+=v[i].second;
            consta++;
            continue;
        }


        else
        {
            if(v[i].second>=q.top() )
            {
                s-=q.top();
                q.pop();
                q.push(v[i].second);
                s+=v[i].second;
            }
        }

    }
    printf("%d\n",s);
}