Cod sursa(job #1894223)

Utilizator MaligMamaliga cu smantana Malig Data 26 februarie 2017 17:06:39
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

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

const int NMax = 100000 + 5;

int N,X,L,runDist,sol;
priority_queue<int> h;

struct elem {
    int val,nr;
}v[NMax];

bool cmp (elem a,elem b) {
    return a.nr>b.nr;
}

int main() {
    in>>N>>X>>L;

    for (int i=1;i<=N;++i) {
        int dist;
        in>>dist>>v[i].val;
        if (X < dist) {
            v[i].nr = 0;
        }
        else if ((X-dist+1) % L == 0) {
            v[i].nr = (X-dist+1) / L;
        }
        else {
            v[i].nr = (X-dist+1) / L + 1;
        }
    }

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

    sol = runDist = 0;

    if (v[1].nr==0) {
        out<<0;
        return 0;
    }

    int i = 1;
    while (i<=N) {
        do {
            h.push(v[i++].val);
        }
        while (i<=N && v[i].nr!=0 && v[i].nr == v[i-1].nr);

        sol += h.top();
        h.pop();
    }

    out<<sol;
    return 0;
}