Cod sursa(job #1227701)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 11 septembrie 2014 13:55:28
Problema Lupul Urias si Rau Scor 12
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <cstdio>
#include <algorithm>
using namespace std;
FILE *f=fopen("lupu.in","r");
FILE *g=fopen("lupu.out","w");
int n,x,l,nr,tot,minim;
int heap[266001];

struct oaie {int dist;
             int lana;};

oaie v[100001];

inline void coboara(int nod)
{int lt=v[heap[nod]].lana;
int lf1=v[heap[nod*2]].lana,lf2=v[heap[nod*2+1]].lana;

if (lt<max(lf1,lf2)) {if (lf1>lf2) {swap(heap[nod],heap[nod*2]);
                                    coboara(nod*2);}
                              else {swap(heap[nod],heap[nod*2+1]);
                                    coboara(nod*2+1);}
                        }
}
inline void urca(int nod)
{if (nod==1) return;
if (v[heap[nod]].lana>v[heap[nod/2]].lana) {swap(heap[nod],heap[nod/2]);
                                             urca(nod/2);}
}



inline bool comp(const oaie &a,const oaie &b)
{if (a.dist>b.dist) return true;
return false;
}

int main()
{int i,j;
fscanf(f,"%d %d %d",&n,&x,&l);
for (i=1;i<=n;i++) fscanf(f,"%d %d",&v[i].dist,&v[i].lana);
sort(v+1,v+n+1,comp);

i=1;
minim=l;

while (i<=n)
{
while (i<=n&&v[i].dist+nr*l<=x&&x-v[i].dist<minim) {heap[i]=i;
                                                    urca(i);
                                                    i++;
                                                    }
minim+=l;
if (heap[1]!=0) {tot+=v[heap[1]].lana;
                 heap[1]=0;
                 coboara(1);
                 nr++;
                 }
while (heap[1]!=0&&v[heap[1]].dist+nr*l>x) {heap[1]=0;
                                            coboara(1);}
}
while (heap[1]!=0)
{nr++;
tot+=v[heap[1]].lana;


heap[1]=0;
coboara(1);
while (heap[1]!=0&&v[heap[1]].dist+nr*l>x) {heap[1]=0;
                                            coboara(1);}
}



fprintf(g,"%d\n",tot);


return 0;}