Pagini recente » Cod sursa (job #557362) | Cod sursa (job #764022) | Cod sursa (job #309482) | Cod sursa (job #1429773) | Cod sursa (job #434607)
Cod sursa(job #434607)
# include <stdio.h>
# include <stdlib.h>
# define MAXN 100000
typedef struct GUTUIE{
long int h,w,tic;
} GUTUIE;
int comparaGutui(const void *aa, const void *bb)
{
GUTUIE* a = (GUTUIE*) aa;
GUTUIE* b = (GUTUIE*) bb;
if (a->tic < b->tic) return -1;
if (a->tic > b->tic) return 1;
if (a->w > b->w ) return 1;
if (a->w < b->w ) return -1;
return 0;
}
GUTUIE gutui[MAXN+1];
long int n,u,h;
//acesta este un MIN-HEAP (contine in varf mereu INDEXUL la cea mai usoara gutuie)
class HEAP{
private:
long int v[MAXN+1];
long int len;
void surface(long int i){
long int aux;
while (i/2 && gutui[v[i]].w < gutui[v[i/2]].w){
aux = v[i]; v[i] = v[i/2]; v[i/2] = aux;
i/=2;
}
}
void submerge(long int i){
long int aux,min;
do{
min = i;
if (2*i <= len && gutui[v[2*i ]].w < gutui[v[min]].w) min = 2*i;
if (2*i+1<= len && gutui[v[2*i+1]].w < gutui[v[min]].w) min = 2*i+1;
if (i==min) break;
aux = v[i]; v[i] = v[min]; v[min] = aux;
i = min;
} while (1);
}
public:
HEAP(){
len = 0;
}
void insert(long int i){
v[++len] = i;
surface(len);
}
long int topWeight(){
return gutui[v[1]].w;
}
long int extract(){
long int sol = v[1];
v[1] = v[len];
len --;
submerge(1);
return sol;
}
long int totalSum(){
long int i, sol = 0;
for (i=1;i<=len;i++)
sol += gutui[v[i]].w;
return sol;
}
};
void citire()
{
FILE *f=fopen("gutui.in","r");
fscanf(f,"%ld%ld%ld",&n,&h,&u);
long int i;
for (i=1;i<=n;i++){
fscanf(f,"%ld%ld",&gutui[i].h,&gutui[i].w);
gutui[i].tic = (h-gutui[i].h)/u + 1;
}
fclose(f);
qsort(gutui+1,n,sizeof(GUTUIE),comparaGutui);
}
void scrie(long int sol)
{
FILE *g=fopen("gutui.out","w");
fprintf(g,"%ld\n",sol);
fclose(g);
}
void calculeaza()
{
HEAP h;
long int i,lasttic = 0;
//iteram prin toate gutuile. Retinem mereu la ce "tic" suntem :D
for (i=1;i<=n;i++){
//daca poti sa o culegi linistit
if (gutui[i].tic > lasttic){
h.insert(i);
lasttic++;
} else if (h.topWeight() < gutui[i].w){ //ai optiunea sa o inlocuiesti cu una pe care deja ai cules'o
h.extract();
h.insert(i);
}
}
scrie(h.totalSum());
}
int main()
{
citire();
calculeaza();
return 0;
}