Cod sursa(job #1515530)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 1 noiembrie 2015 19:14:31
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.41 kb
#include <cstdio>
#include <algorithm>
#define LIM 100023
using namespace std;
long long t[LIM],heap[LIM];
long long a[LIM];
struct str
{
    long long val;
    long long pos;
}srt[LIM];
long long n,x,l,temp,m,lmt;
long long tata(long long a)
{
    return a/2;
}
void checkup(long long pos)
{
    while(tata(pos)!=0&&a[heap[pos]]>a[heap[tata(pos)]])
    {
        swap(heap[pos],heap[tata(pos)]);
        pos=tata(pos);
        if(pos==0) return;
    }
}
void add(long long pos)
{
    heap[++m]=pos;
    checkup(m);
}
void checkdown()
{
    long long nod=1;
    while(nod<=m)
    {
        long long best=0;
        long long st=nod*2,dr=nod*2+1;
        if(st<=m&&a[heap[nod]]<a[heap[st]]) best=1;
        if(best==0&&dr<=m&&a[heap[nod]]<a[heap[dr]]) best=2;
        if(best==1&&dr<=m&&a[heap[st]]<a[heap[dr]]) best=2;
        if(best==0) return;
        if(best==1)
        {
            swap(heap[nod],heap[st]);
            nod=st;
        }
        else if(best==2)
        {
            swap(heap[nod],heap[dr]);
            nod=dr;
        }
    }
}
void rem()
{
    swap(heap[1],heap[m]);
    m--;
    if(m==0) return;
    checkdown();
}
long long comp(str a,str b)
{
    return a.val>b.val;
}
int main()
{
    freopen ("lupu.in","r",stdin);
    freopen ("lupu.out","w",stdout);
    scanf("%lld%lld%lld",&n,&x,&l);
    lmt=x/l+2;
    for(long long i=1;i<=n;i++)
    {
        ++temp;
        scanf("%lld%lld",&t[temp],&a[temp]);
        while(t[temp]>x)
        {
            scanf("%lld%lld",&t[temp],&a[temp]);
        }
        t[i]=(x-t[i])/l+1;
    }
    for(long long i=1;i<=temp;i++)
    {
        srt[i].val=t[i];
        srt[i].pos=i;
    }
    n=temp;
    sort(srt+1,srt+temp+1,comp);
  //  for(long long i=1;i<=temp;i++)
 //   {
 //       printf("%d %d %d\n",srt[i].pos,srt[i].val,a[srt[i].pos]);
//    }
    long long pst=1;
    long long sum=0;
  //  printf("%d\n",lmt);
    for(long long i=lmt;i>=1;i--)
    {
      ///  printf("%d %d\n",srt[pst].pos,i);
        if(srt[pst].val==i&&pst<=n)
        {
            while(srt[pst].val==i)
            {
                add(srt[pst].pos);
                pst++;
                if(pst>n) break;
            }
        }
        if(m>=1)
        {
               // printf("%d\n",a[heap[1]]);
            sum+=a[heap[1]];
            rem();
        }
    }
    printf("%lld\n",sum);
}