Cod sursa(job #2072643)

Utilizator xRoALexBirtoiu Alexandru xRoALex Data 22 noiembrie 2017 00:07:56
Problema Lupul Urias si Rau Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;


FILE * in = fopen("lupu.in","r");
FILE * out = fopen("lupu.out","w");

vector < pair<int,int> > v;

struct cmp2
{
    bool operator () (const int &a,const int &b)
    {
        return a>b;
    }
};

int n,x,l,s=0;

inline bool cmp(pair<int,int> a, pair<int,int> b)
{
    if(a.first == b.first)
        return a.second>b.second;
    return a.first>b.first;
}

priority_queue <int,vector<int>,cmp2> heap;

int main()
{
    fscanf(in,"%d%d%d",&n,&l,&x);
    for(int i=1; i<=n; i++)
    {
        int x,y;
        fscanf(in,"%d%d",&x,&y);
        v.push_back({x,y});
    }
    sort(v.begin(),v.end(),cmp);

    for(int i=0;i<v.size();i++)
    {
        if(v[i].first<=l)
            {
            if(v[i].first+x*(heap.size())<=l)
                {
                    s+=v[i].second;
                    heap.push(v[i].second);
                }
                else
                {
                    heap.push(v[i].second);
                    s+=v[i].second;
                    s-=heap.top();
                    heap.pop();
                }
            }
    }
    fprintf(out,"%d",s);
    return 0;
}