Cod sursa(job #1630211)

Utilizator AnaRaduAna-Maria Radu AnaRadu Data 4 martie 2016 23:25:05
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <stdio.h>
#include <algorithm>
#define lim 100005
using namespace std;
struct elem{int dist,val;};
elem v[lim];
int heap[lim],ind[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;
    ind[heap[p]]=p;
    ind[heap[q]]=q;
}
void urca(int p){
    while(p>0&&v[heap[p]].val>v[heap[tata(p)]].val){
        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&&v[heap[fiust(p)]].val>v[heap[q]].val)
            q=fiudr(p);
        if(v[heap[q]].val>v[heap[p]].val){
            schimba(p,q);
            p=q;
        }
        else
            pp=0;
    }
}
void sterge(int p){
    m--;
    schimba(m,p);
    if(p>0&&v[heap[p]].val>v[heap[tata(p)]].val)
        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,k,l,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);
    sort(v+1,v+n+1,cmp);
    k=raza/x;
    i=1;
    l=1;
    for(j=k;j>=0;j--){
        while(v[i].dist+j*x>raza){
            sterge(ind[i]);
            l++;
        }
        while(i<=n&&v[i].dist+j*x<=raza){
            adauga(i);
            i++;
        }
        if(m>0){
            rasp=rasp+(long long)v[heap[0]].val;
            sterge(0);
        }
    }
    fprintf(fout,"%I64d",rasp);
    fclose(fin);
    fclose(fout);
    return 0;
}