Cod sursa(job #1485791)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 12 septembrie 2015 23:29:08
Problema Lupul Urias si Rau Scor 12
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 2.2 kb
#include <cstdio>
#include <algorithm>
#define LIM 100023
using namespace std;
int t[LIM],a[LIM],heap[LIM];
struct str
{
    int val;
    int pos;
}srt[LIM];
int n,x,l,temp,m,lmt;
int tata(int a)
{
    return a/2;
}
void checkup(int 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(int pos)
{
    heap[++m]=pos;
    checkup(m);
}
void checkdown()
{
    int nod=1;
    while(nod<=m)
    {
        int best=0;
        int st=nod*2,dr=nod*2+1;
        if(st<=m&&a[heap[nod]]<a[heap[st]]) best=1;
        if(dr<=m&&a[heap[nod]]<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();
}
int comp(str a,str b)
{
    return a.val>b.val;
}
int main()
{
    freopen ("lupu.in","r",stdin);
    freopen ("lupu.out","w",stdout);
    scanf("%d%d%d",&n,&x,&l);
    lmt=x/l+1;
    for(int i=1;i<=n;i++)
    {
        ++temp;
        scanf("%d%d",&t[temp],&a[temp]);
        while(t[i]>x)
        {
            scanf("%d%d",&t[temp],&a[temp]);
        }
        t[i]=(x-t[i])/l+1;
    }
    for(int i=1;i<=temp;i++)
    {
        srt[i].val=t[i];
        srt[i].pos=i;
    }
    temp--;
    n=temp;
    sort(srt+1,srt+temp+1,comp);
  //  for(int i=1;i<=temp;i++)
 //   {
 //       printf("%d %d %d\n",srt[i].pos,srt[i].val,a[srt[i].pos]);
//    }
    int pst=1;
    int sum=0;
  //  printf("%d\n",lmt);
    for(int i=lmt;i>=1;i--)
    {
      ///  printf("%d %d\n",srt[pst].pos,i);
        if(srt[pst].val==i)
        {
            while(srt[pst].val==i)
            {
                add(srt[pst].pos);
                pst++;
            }
            if(m>=1)
            {
               // printf("%d\n",a[heap[1]]);
                sum+=a[heap[1]];
                rem();
            }
        }
    }
    printf("%d\n",sum);
}