Cod sursa(job #992132)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 1 septembrie 2013 09:52:43
Problema Lupul Urias si Rau Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

#define maxn 100005

using namespace std;

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

vector <int> V[maxn];
int moments[maxn];
bool picked[maxn];

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

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

priority_queue <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)
    {
        m = (x-v[i].d)/l;

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

        if (!picked[m])
        {
            moments[++t] = m;
            picked[m] = 1;
        }
        V[m].push_back(v[i].x);
    }

    sort (moments+1, moments+t+1);

    cnt = moments[t],i=t;

    for (cnt = moments[t]; cnt>=0; --cnt)
    {
        if (cnt >= moments[i])
        {
            for (int j=0; j<V[moments[i]].size(); ++j)
            {
                H.push(V[moments[i]][j]);
            }
            --i;
        }

        s+=H.top();
        H.pop();
    }

    fout<<s;
}