Cod sursa(job #1776827)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 11 octombrie 2016 20:39:29
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
struct SHEEP{
    int wool, time;
};
priority_queue<int> heap;
vector<SHEEP>v[MAXN + 5];
int main(){
    freopen("lupu.in", "r", stdin);
    freopen("lupu.out", "w", stdout);
    int n, x, l, d, a, i, j;
    long long s = 0;
    SHEEP aux;
    scanf("%d%d%d", &n, &x, &l);
    for (i = 1; i <= n; i ++){
        scanf("%d%d", &d, &a);
        if (d > x)
            continue;
        aux.wool = a;
        aux.time = min((x - d) / l + 1, n);
        v[aux.time].push_back(aux);
    }
    for (i = n; i >= 1; i --){
        for (j = 0; j < v[i].size(); j ++)
            heap.push(v[i][j].wool);
        if (!heap.empty()){
            s += heap.top();
            heap.pop();
        }
    }
    printf("%lld\n", s);
    return 0;
}