Cod sursa(job #1804366)

Utilizator KronSabau Valeriu Kron Data 12 noiembrie 2016 15:04:13
Problema Lupul Urias si Rau Scor 88
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <algorithm>
#define Nmax 100010
using namespace std;
ifstream f("lupu.in");
ofstream g("lupu.out");
long long  n,Dmax,l,sum;
long long lana[Nmax],t[Nmax],Tmax;
int ind[Nmax];
bool ins[Nmax];
priority_queue<long long >pq;
int cmp(int a,int b)
{
    return t[a]<t[b];
}
int main()
{
    f >> n >> Dmax >> l;
    int x;
    for(int i=1;i<=n;i++){
        f >> x >> lana[i];
        ind[i]=i;
        t[i]=(Dmax-x)/l;
        Tmax=max(t[i],Tmax);
    }
    sort(ind+1,ind+n+1,cmp);
    int j=n;
    for(int i=Tmax;i>=0;i--)
    {
        while(t[ind[j]]==i && j>0){

                ins[ind[j]]=1;
                pq.push(lana[ind[j]]);
                j--;
            }
            if(!pq.empty())
                sum+=pq.top();
            pq.pop();
    }

    g << sum;

    return 0;
}