Cod sursa(job #1847544)

Utilizator DanielRusuDaniel Rusu DanielRusu Data 14 ianuarie 2017 18:31:36
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>

using namespace std;

#define DIM 100004

priority_queue <int> Q;

struct sh {
    int w;
    int time;
} sheep[DIM];

bool cmp(sh a, sh b) {
    return a.time > b.time;
}

int main() {
    freopen("lupu.in","r",stdin);
    freopen("lupu.out","w",stdout);

    int N, X, L;

    scanf("%d %d %d\n", &N, &X, &L);

    int dist, wool;
    int ts = 0;
    for(int i = 1; i <= N; ++i) {
        scanf("%d %d\n", &dist, &wool);

        if(X < dist) continue;

        int when = max(X - dist, 0) / L + 1;
        sheep[++ts].time = when;
        sheep[ts].w = wool;
    }

    sort(sheep + 1, sheep + 1 + ts, cmp);

    sheep[++ts].time = 0;
    sheep[ts].w = 0;

    long long ans = 0;
    for(int i = 1; i <= ts; ++i) {
        int j = i;

        while(sheep[i].time == sheep[j].time) {
            Q.push(sheep[j].w);
            ++j;
        }

        int toDelete = sheep[i].time - sheep[j].time;

        while(!Q.empty() && toDelete) {
            --toDelete;
            ans += (long long)Q.top();
            Q.pop();
        }

        i = (j == ts ? j : j - 1);
    }

    cout << ans << '\n';

    return 0;
}