Cod sursa(job #775723)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 8 august 2012 19:10:38
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 0.86 kb
#include <fstream>
#include <algorithm>
#include <queue>
#define PI pair <int, int>
#define t first
#define c second
#define N 100010

using namespace std;

ifstream f("gutui.in");
ofstream g("gutui.out");


struct VecCompare
{
    bool operator() (const PI &a, const PI &b) const
    {
        return a.t>b.t;
    }
};

priority_queue <int> Q;

int n,x,l,i,j,T=0;
PI V[N];
long long ANS;

int main ()
{
    f >> n >> x >> l;
    for (i=1;i<=n;i++)
    {
        f >> V[i].t >> V[i].c;
        V[i].t=(x-V[i].t)/l;
    }
    sort(V+1,V+n+1,VecCompare());
    T=V[1].t;
    for (i=T,j=1;i>=0;i--)
    {
        for (;j<=n && V[j].t==i;j++)
            Q.push(V[j].c);
        if (!Q.empty())
        {
            ANS+=Q.top()*1LL;
            Q.pop();
        }
    }
    g << ANS << '\n';
    f.close();g.close();
    return 0;
}