Cod sursa(job #1631793)

Utilizator AnaRaduAna-Maria Radu AnaRadu Data 5 martie 2016 18:58:09
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <stdio.h>
#include <algorithm>
#define lim 100005
using namespace std;
struct elem{int dist,val;};
elem v[lim];
int heap[lim],m;
int tata(int p){
    return (p-1)/2;
}
int fiust(int p){
    return 2*p+1;
}
int fiudr(int p){
    return 2*p+2;
}
void schimba(int p,int q){
    int aux;
    aux=heap[p];
    heap[p]=heap[q];
    heap[q]=aux;
}
void urca(int p){
    while(p>0&&heap[p]>heap[tata(p)]){
        schimba(p,tata(p));
        p=tata(p);
    }
}
void adauga(int x){
    heap[m]=x;
    m++;
    urca(m-1);
}
void coboara(int p){
    int q,pp=1;
    while(pp==1&&fiust(p)<m){
        q=fiust(p);
        if(fiudr(p)<m&&heap[fiust(p)]>heap[q])
            q=fiudr(p);
        if(heap[q]>heap[p]){
            schimba(p,q);
            p=q;
        }
        else
            pp=0;
    }
}
void sterge(int p){
    m--;
    schimba(m,p);
    if(p>0&&heap[p]>heap[tata(p)])
        urca(p);
    else
        coboara(p);
}
bool cmp(elem a,elem b){
    if(a.dist<b.dist)
        return true;
    else
        return false;
}
int main(){
    FILE *fin,*fout;
    fin=fopen("lupu.in","r");
    fout=fopen("lupu.out","w");
    int i,j,n,raza,x;
    long long rasp=0;
    fscanf(fin,"%d%d%d",&n,&raza,&x);
    for(i=1;i<=n;i++){
        fscanf(fin,"%d%d",&v[i].dist,&v[i].val);
        v[i].dist=(raza-v[i].dist)/x;
    }
    sort(v+1,v+n+1,cmp);
    i=n;
    for(j=v[n].dist;j>=0;j--){
        /*while(v[i].dist>=j){
            sterge(ind[i]);
            l++;
        }*/
        while(i<=n&&v[i].dist>=j){
            adauga(v[i].val);
            i--;
        }
        if(m>0){
            rasp=rasp+(long long)heap[0];
            sterge(0);
        }
    }
    fprintf(fout,"%I64d",rasp);
    fclose(fin);
    fclose(fout);
    return 0;
}