Cod sursa(job #1257420)

Utilizator DjokValeriu Motroi Djok Data 7 noiembrie 2014 18:57:01
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul II Marime 1 kb
#include<fstream>
#include<algorithm>
using namespace std;

typedef struct lol {
        int x,y;
}troll;

int i,j,n,nr,x,l,h[100005];
long long rs;
troll a[100005];

void upheap() {
     int nod=nr;
     while(nod>1 && h[nod]>h[nod/2])
     swap(h[nod],h[nod/2]),nod/=2;
}

void downheap() {
     int nod=1;
     while(2*nod<=nr)
     {
       int index=nod;
       if(h[nod]<h[2*nod]) index=2*nod;
       if(2*nod<nr && h[index]<h[2*nod+1]) index=2*nod+1;

       if(index==nod) break;
       else swap(h[nod],h[index]),nod=index;
     }
}

bool cmp(const troll &a,const troll &b) {
     return a.x>b.x;
}

int main()
{
  ifstream cin("lupu.in");
  ofstream cout("lupu.out");

  cin>>n>>x>>l;
  for(i=1;i<=n;++i)
  {
    cin>>j>>a[i].y;
    a[i].x=(x-j)/l;
  }

  sort(a+1,a+n+1,cmp);

  for(i=a[1].x,j=1;i>=0;--i)
  {
    while(a[j].x==i && j<=n) h[++nr]=a[j].y,upheap(),++j;

    if(nr) rs+=h[1],h[1]=h[nr--],downheap();
  }

  cout<<rs<<'\n';

 return 0;
}