Cod sursa(job #1244609)

Utilizator DjokValeriu Motroi Djok Data 17 octombrie 2014 21:01:52
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.05 kb
#include<fstream>
#include<algorithm>
using namespace std;

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

int i,j,g,n,h,u,nr,heap[100005];
long long rs;
troll a[100005];

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

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

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

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

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

  cin>>n>>h>>u;
  for(i=1;i<=n;++i)
  {
    cin>>j>>a[i].y;
     a[i].x=(h-j)/u;
    g=max(g,a[i].x);
  }

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

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

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

  cout<<rs<<'\n';

 return 0;
}