Cod sursa(job #1233161)

Utilizator BlueStrutAndrei Prahoveanu BlueStrut Data 24 septembrie 2014 21:07:44
Problema Lupul Urias si Rau Scor 92
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include<cstdio>
#include<algorithm>
using namespace std;
pair<int,int> oaie[100001];
int i, n, x, l, d, a[100001], crt, mx, k;
long long sum;
void swap(int &a, int &b){int aux; aux=a; a=b; b=aux;}
void heap_down(int poz, int n){
    if (2*poz<=n) {
        if (2*poz+1<=n) {if ((a[2*poz]>a[poz])||(a[2*poz+1]>a[poz])){
            if (a[2*poz]>a[2*poz+1]) {
                swap(a[poz], a[2*poz]); heap_down(2*poz, n);
            } else {
                swap(a[poz], a[2*poz+1]); heap_down(2*poz+1, n);
            }}
        } else if (a[2*poz]>a[poz]) swap(a[poz], a[2*poz]);
    }
}
void heap_up(int poz){
    if ((poz>1)&&(a[poz]>a[poz/2])) {
        swap(a[poz], a[poz/2]);
        heap_up(poz/2);
    }
}
int main(){
    freopen("lupu.in","r",stdin);
    freopen("lupu.out","w",stdout);
    scanf("%d%d%d", &n, &x, &l); crt=0; sum=0;
    for (i=1;i<=n;i++) {
        scanf("%d%d", &d, &oaie[++crt].second);
        if (d>x) {crt--; continue;}
        oaie[i].first=(x-d)/l;
        if (oaie[i].first>mx) mx=oaie[i].first;
    }
    sort(oaie+1, oaie+crt+1); k=crt;
    for (i=mx;i>=0;i--) {
        while ((oaie[k].first>=i)&&(k>0)) {
            a[++a[0]]=oaie[k].second; heap_up(a[0]); k--;
        }
        if (a[0]>0) {sum+=a[1]; swap(a[1], a[a[0]]); a[0]--; heap_down(1, a[0]);}
    }
    printf("%lld\n", sum); return 0;
}