Cod sursa(job #1630126)

Utilizator AnaRaduAna-Maria Radu AnaRadu Data 4 martie 2016 22:31:26
Problema Lupul Urias si Rau Scor 24
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <stdio.h>
#include <algorithm>
#define lim 100005
using namespace std;
struct elem{int poz,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.poz<b.poz)
        return true;
    else
        return false;
}
int main(){
    FILE *fin,*fout;
    fin=fopen("lupu.in","r");
    fout=fopen("lupu.out","w");
    int i,j,k,n,raza,x,rasp=0;
    fscanf(fin,"%d%d%d",&n,&raza,&x);
    for(i=1;i<=n;i++)
        fscanf(fin,"%d%d",&v[i].poz,&v[i].val);
    sort(v+1,v+n+1,cmp);
    k=raza/x;
    i=1;
    for(j=k;j>=0;j--){
        while(i<=n&&v[i].poz+j*x<=raza){
            adauga(v[i].val);
            i++;
        }
        if(m>0){
            rasp+=heap[0];
            sterge(0);
        }
    }
    fprintf(fout,"%d",rasp);
    fclose(fin);
    fclose(fout);
    return 0;
}