Cod sursa(job #477437)

Utilizator andra23Laura Draghici andra23 Data 14 august 2010 16:32:47
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include<iostream>
#include<fstream>
#include<algorithm>

using namespace std;
pair <int, int> a[100010];
long long s;
int h[100010], m;

void shift(int k){
    int son, aux;
    do {
        son = 0;
        if (k*2 <= m){
            son = k*2;
            if (k*2+1 <= m && h[k*2+1] > h[son])
                son = k*2+1;
            if (h[k] >= h[son])
                son = 0;   
        }
        if (son){
            aux = h[k];
            h[k] = h[son];
            h[son] = aux;
            k = son;
        }
    } while (son);
}

void percolate(int k){
    int x = h[k];
    while (k > 1 && h[k/2] < x){
        h[k] = h[k/2];
        k = k/2;
    }    
    h[k] = x;
}

void insert(int x){
    m++;
    h[m] = x;
    percolate(m); 
}

int max(){
    if (m == 0)
        return 0;
    else {
        int x = h[1];
        h[1] = h[m];
        m--;
        shift(1);
        return x;
    }
}

int main(){
    ifstream f("lupu.in");
    ofstream g("lupu.out");
    int n, x, l, i, p, q;
    f>>n>>x>>l;
    for (i = 1; i <= n; i++){
        f>>p>>q;
        a[i] = make_pair(p, q);
    }
    
    sort(a+1, a+n+1); 
    int ap = (x - a[1].first)/l;  
    int dist, j = 1;
    
    for (i = ap; i >= 0; i--){
        dist = x - i*l;
        while (j <= n && a[j].first <= dist){
            insert(a[j].second); 
            j++;
        }
        s = s + max();
    }
    
    g<<s<<'\n';
    
    return 0;
}