Cod sursa(job #1815540)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 25 noiembrie 2016 13:15:32
Problema Lupul Urias si Rau Scor 48
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <cstdio>
#include <algorithm>

using namespace std;
pair <int,int> v[100001];
int h[100001];
int cmp (pair <int,int> a,pair <int,int> b){
    return a.first>b.first;
}
void adauga (int i,int elem){
    int p,c,aux;
    h[elem]=v[i].second;
    c=elem;
    p=elem/2;
    while (p>0){
        if (h[c]>h[p]){
            aux=h[c];
            h[c]=h[p];
            h[p]=aux;
        }
        else break;
        c=p;
        p/=2;
    }
}
void sterge (int poz,int elem){
    int p,c,aux;
    h[poz]=h[elem];
    p=poz;
    c=2*poz;
    while (c<elem && h[p]<h[c]){
        if (c+1<elem && h[c+1]>h[c])
            c++;
        aux=h[c];
        h[c]=h[p];
        h[p]=aux;
        p=c;
        c*=2;
    }

}
int main()
{
    FILE *fin=fopen ("lupu.in","r");
    FILE *fout=fopen ("lupu.out","w");
    int n,x,l,i,elem=0,j,m=0,a,b;
    long long sol=0;
    fscanf (fin,"%d%d%d",&n,&x,&l);
    for (i=1;i<=n;i++){
        fscanf (fin,"%d%d",&a,&b);
        if (x>=a){
            m++;
            v[m].first=(x-a)/l+1;
            v[m].second=b;
        }
        // dupa v[i].first alegeri, oaia i va disparea
    }
    sort (v+1,v+m+1,cmp);
    j=1;
    for (i=v[1].first;i>0;i--){
        while (j<=m && v[j].first==i){
            elem++;
            adauga (j,elem);
            j++;
        }
        if (elem){
            sol+=h[1];
            sterge (1,elem);
            elem--;
        }
    }
    fprintf (fout,"%lld",sol);
    return 0;
}