Cod sursa(job #1150814)

Utilizator jul123Iulia Duta jul123 Data 23 martie 2014 16:09:20
Problema Lupul Urias si Rau Scor 72
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

int l=1, heap[100000];
typedef struct {
int a;
int d;
int t;
}oaie;
oaie o[100000];
void urca(int heap[], int poz)
{
    while(poz>1 && o[heap[poz]].a > o[heap[poz/2]].a)
        {swap(heap[poz], heap[poz/2]);
        poz/=2;
    }
}
void coboara(int heap[], int &n, int poz)
{
    if(2*poz>n) return;
    int poz1=2*poz;
    if(poz1+1<=n && o[heap[poz1]].a<o[heap[poz1+1]].a)
        poz1++;
    if(o[heap[poz1]].a > o[heap[poz]].a)
    {
        swap(heap[poz1], heap[poz]);
        coboara(heap, n, poz1);
    }
}
void inserare(int heap[], int &n, int val)
{
    n++;
    heap[n]=l;
    urca(heap, n);
    l++;
}

void el_varf(int heap[],int &n)
{
    heap[1]=heap[n--];
    coboara(heap, n, 1);
}
int cmp(oaie x, oaie y) {
    return (x.t>y.t);
}
int main()
{
    FILE *fin, *fout;
    fin=fopen("lupu.in", "r");
    fout=fopen("lupu.out", "w");

    int maxim, s, n, x, ll, i, j, nr=0;
    maxim=0;
    s=0;
    fscanf(fin, "%d %d %d", &n, &x, &ll);
    for(i=1; i<=n; i++)
    {
        fscanf(fin, "%d %d", &o[i].d, &o[i].a);
        o[i].t=(x-o[i].d)/ll+1;
        if(o[i].t>maxim)
            maxim=o[i].t;
    }
    sort(o+1, o+n+1, cmp);
    /*for(i=1; i<=n; i++)
        cout<<o[i].t<<" ";*/
    for(i=maxim; i>=1; i--){
        while(o[l].t==i) {
            inserare(heap, nr, l);
        }
        s+=o[heap[1]].a;
        //cout<<nr<<" "<<o[heap[1]].a<<" ";
        el_varf(heap, nr);
    }
    fprintf(fout, "%d", s);

}