Cod sursa(job #1318545)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 16 ianuarie 2015 04:02:40
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 0.96 kb
#include <fstream>
#include <algorithm>
#include <queue>
#include <vector>

#define maxn 100005

using namespace std;

ifstream fin("lupu.in");
ofstream fout("lupu.out");

struct sheep
{
    int x,d;
}v[maxn];

int n,x,l,m,t,cnt,i;
long long s;

bool cmp (const sheep &a, const sheep &b)
{
    return a.d<b.d;
}

priority_queue< int , vector<int> , less<int> > H;

int main()
{
    fin>>n>>x>>l;
    for (i=1; i<=n; ++i)
        fin>>v[i].d>>v[i].x;

    for (i=1; i<=n; ++i)
    {
        v[i].d = (x-v[i].d)/l;

        if (x-v[i].d<0) v[i].d=-1;
        if (v[i].d>100000) v[i].d=100001;
    }

    sort (v+1, v+n+1, cmp);

    i=n;
    v[0].d=-1;

    for (cnt = v[n].d; cnt>=0; --cnt)
    {
        while (cnt <= v[i].d)
            {
                H.push (v[i].x);
                --i;
            }

        if (!H.empty())
        {
            s+=H.top();
            H.pop();
        }
    }

    fout<<s;
}