Cod sursa(job #1557411)

Utilizator LucianTLucian Trepteanu LucianT Data 27 decembrie 2015 14:54:32
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#define maxN 1000004
using namespace std;
vector<int> v[maxN];
int n, x, l, i, j, d, a, t;
int lg;
long long s;
int heap[maxN];
int heap_top()
{
    return heap[1];
}
void heap_push(int x)
{
    int tata, fiu;
    lg++;
    fiu = lg, tata = fiu/2;
    while(tata > 0)
    {
        if(heap[tata] < x)
        {
            heap[fiu ]= heap[tata];
            fiu = tata;
            tata /= 2;
        }
        else break;
    }
    heap[fiu] = x;
}
void heap_pop()
{
    int tata, fiu, x;
    tata = 1, fiu = 2*tata;
    x = heap[lg--];
    while(fiu <= lg)
    {
        if(heap[fiu] < heap[fiu+1] && fiu < lg) fiu++;
        if(x < heap[fiu])
        {
            heap[tata] = heap[fiu];
            tata = fiu;
            fiu *= 2;
        }
        else break;
    }
    heap[tata] = x;
}
int main()
{
    freopen("lupu.in", "r", stdin);
    freopen("lupu.out", "w", stdout);
    scanf("%d %d %d", &n, &x, &l);
    for(i = 1; i <= n; i++)
    {
        scanf("%d %d", &d, &a);
        if(d > x) t = 0;
        else t = 1 + (x-d)/l;
        v[t].push_back(a);
    }
    for(i = maxN; i >= 1; i--)
    {
        if(!v[i].empty())
        {
            for(j = 0; j < (int)v[i].size(); j++)
                heap_push(v[i][j]);
        }
        if(lg)
            s += heap_top(), heap_pop();
    }
    printf("%lld", s);
    return 0;
}