Cod sursa(job #848709)

Utilizator chimistuFMI Stirb Andrei chimistu Data 5 ianuarie 2013 18:26:15
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <cstdio>
#include <cstdlib>
#define maxn 100001
#include <iostream>
using namespace std;
FILE*f=fopen("lupu.in","r");
FILE*g=fopen("lupu.out","w");

int n,x,l,d,heap[maxn],Tmax,indheap;
long long s;

typedef struct
{int t;
int l;}oaie;

oaie A[maxn];

bool comp(oaie a ,oaie b)
{
    return  a.t < b.t;
}

int max(int a,int b)
{
    if (a>b)
       return a;
    return b;
}

void swap(int &a,int &b)
{
     int aux;
     aux=a;
     a=b;
     b=aux;
     }

void up_heap(int x)
{
     if (x==1)
        return;
     if (heap[x/2]<heap[x])
     {
             swap(heap[x/2],heap[x]);
             up_heap(x/2);
             }
}

void down_heap(int x)
{
     int m=x;
     if ((2*x<=indheap) && (heap[2*x]>heap[x]))
        m=2*x;
     if ((2*x+1<=indheap) && (heap[2*x+1]>heap[x]))
        m=2*x+1;
     if (m!=x)
     {
         swap(heap[m],heap[x]);
         down_heap(m);
         }
}

int main()
{
    int k,x,l,i,j;
    fscanf(f,"%d%d%d",&n,&x,&l);
    s=0;
    for (i=1;i<=n;i++)
    {
          fscanf(f,"%d%d",&d,&A[i].l);
          A[i].t=(x-d)/l+1;
          }
    sort(A+1,A+n+1,comp);
    Tmax=A[n].t;
    indheap=0;j=n;
    for (i=Tmax;i>0;i--)
    {
        while ((j>0) && (A[j].t==i))
        {
                 indheap++;
                 heap[indheap]=A[j].l;
                 up_heap(indheap);
                 j--;
                  }
        if (indheap!=0)
        {
              s+=heap[1];
              swap(heap[1],heap[indheap]);
              indheap--;
              down_heap(1);
              }
    }
    fprintf(g,"%lld",s);
    return 0;
}