Cod sursa(job #1244688)

Utilizator rangerChihai Mihai ranger Data 17 octombrie 2014 23:28:16
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.23 kb
#include<fstream>
#include<set>
#include<algorithm>
using namespace std;
const int nmax=100010;
struct gutui{
 int g,h;};
 gutui a[nmax];

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

 bool cmp(gutui g1,gutui g2)
 { return g1.h<g2.h;}
 int n,i,u,h,p; long long res;
 int heap[nmax], heap_size;

 void coboara(int nod)
 {
     int son=0;
     if (2*nod<=heap_size) son=2*nod;
     if (2*nod+1<=heap_size && heap[2*nod+1]>heap[2*nod]) son=2*nod+1;
     if (heap[nod]>=heap[son] || !son) return;
     swap(heap[nod],heap[son]);
     coboara(son);
 }

 void urca(int nod)
 {
     while (nod>1 && heap[nod]>heap[nod/2])
        swap(heap[nod],heap[nod/2]),nod/=2;
 }

 void h_insert(int val)
 {
     heap[++heap_size]=val;
     urca(heap_size);
 }

 void h_erase()
 {
     swap(heap[1],heap[heap_size]);
     heap_size--;
     coboara(1);
 }
 int main()
 {
     cin>>n>>h>>u;
     for (i=1;i<=n;i++) cin>>a[i].h>>a[i].g;
     sort(a+1,a+n+1,cmp);


     p=h;
     while (p>=a[1].h) p-=u;
     p+=u;
     i=1;

    while (p<=h) {
        while (a[i].h<=p && i<=n) h_insert(a[i].g),i++;
        p+=u;
        if (heap_size)res+=heap[1],h_erase();
     }
     cout<<res;
     return 0;
 }