Cod sursa(job #1894964)

Utilizator MaligMamaliga cu smantana Malig Data 27 februarie 2017 18:14:24
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 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;
long long sol;
priority_queue<int> h;

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

bool cmp (elem a,elem b) {
    return a.dist<b.dist;
}

const int strMax = 100005 * 30;
char str[strMax];
int pos = 0;

int getNumber() {
    int nr = 0;
    while (!('0'<=str[pos] && str[pos]<='9')) {
        ++pos;
    }

    while ('0'<=str[pos] && str[pos]<='9') {
        nr = nr * 10 + str[pos++] - '0';
    }
    return nr;
}

int main() {
    in.getline(str,strMax,'%');
    N = getNumber();
    X = getNumber();
    L = getNumber();

    for (int i=1;i<=N;++i) {
        v[i].dist = getNumber();
        v[i].val = getNumber();
    }

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

    int minDist = v[1].dist;
    if (minDist > X) {
        cout<<0;
        return 0;
    }

    int rem = (X - minDist)/L;
    int addedDistance = rem*L;

    int i = 1;
    while (0<=addedDistance) {
        while (i<=N && (v[i].dist + addedDistance <= X)) {
            h.push(v[i++].val);
        }

        if (!h.empty()) {
            sol += h.top();
            h.pop();
        }

        addedDistance -= L;
    }

    out<<sol;
    return 0;
}