Cod sursa(job #852731)

Utilizator chimistuFMI Stirb Andrei chimistu Data 11 ianuarie 2013 17:47:37
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <cstdio>
#include <cstdlib>
#define maxn 100001
#include <algorithm>
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)
        if (heap[x/2]<heap[x])
        {
            swap(heap[x/2],heap[x]);
            up_heap(x/2);
            }
}

void down_heap(int x)
{
     int m;
     if (2*x<=indheap)
     {
           m=2*x;
           if (2*x+1<=indheap && heap[2*x+1]>heap[2*x])
              m=2*x+1;
           if (heap[m]>heap[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;
}