Cod sursa(job #1309403)

Utilizator andreeadeacAndreea Ioana Deac andreeadeac Data 5 ianuarie 2015 18:47:59
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <fstream>
#include<algorithm>
using namespace std;

ifstream in("lupu.in");
ofstream out("lupu.out");
struct oi{ int t, c;} v[100001];
int n,l,maxd,nr;
long long heap[100001];

bool cmp(oi a, oi b){
    return a.t<b.t;
}
void schimba (int x, int y){
    int a=heap[x];
    heap[x]=heap[y];
    heap[y]=a;
}
void urcare(int i){
    while(i>=2 && heap[i] < heap[i/2]){
        schimba(i,i/2);
        i/=2;
    }
}
void coborare(int i){
     int fs = 2*i, fd = 2*i + 1, bun = i;
    if (fs <= nr && heap[fs] < heap[bun])
        bun = fs;
    if (fd <= nr && heap[fd] < heap[bun])
        bun = fd;
    if (bun != i) {
        schimba(i, bun);
        coborare(bun);
    }
}
int main()
{
    in>>n>>maxd>>l;
    int i,x;
    for(i=1;i<=n;i++){
        in>>x>>v[i].c;
        v[i].t=(maxd-x)/l;
    }
    sort(v,v+n+1,cmp);
    heap[++nr]=v[1].c;
    for(i=2;i<=n;i++){
        if(nr<=v[i].t){
            heap[++nr]=v[i].c;
            urcare(nr);
            //out<<v[i].t<<" "<<v[i].c<<"\n";
        }
        else{
            if(v[i].c>heap[1]){
                heap[1]=v[i].c;
                coborare(1);
                //out<<v[i].t<<" "<<v[i].c<<"\n";
            }
        }
    }
    long long s1=0;
    for(i=1;i<=nr;i++){
        s1+=heap[i];
        //out<<heap[i]<<" ";
    }
    out<<s1;
    return 0;
}