Cod sursa(job #335330)

Utilizator marinMari n marin Data 29 iulie 2009 16:17:10
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <stdio.h>
#define DIM 100101

struct nod {
	int inf;
	nod *adr;
};

nod *T[DIM],*q;

int H[2*DIM];
int dH,N,X,D,A,L,S,t,i;

void baga(int x){
	int c,p,aux;
	H[++dH] = x;
	c = dH;
	p = c/2;
	while(p && H[p]<H[c]) {
		aux = H[p];
		H[p] = H[c];
		H[c] = aux;
		c = p;
		p = c/2;
	}
}

void scoate(){
	H[1] = H[dH];
	dH--;
	
	
	int p = 1;
	int c = 2;
	int aux;
	while (c<=dH) {
		if (c+1 <= dH && H[c]>H[c+1])
			c++;
		if (H[c]<H[p]) {
			aux = H[p];
			H[p] = H[c];
			H[c] = aux;

			p = c;
			c = 2*p;
		} else break;
	}
	
}

int main(){
	FILE *f = fopen("lupu.in","r");
	fscanf(f,"%d %d %d", &N, &X, &L);
	for (i=1;i<=N;i++) {
		fscanf(f,"%d %d",&D, &A);
		if (D>X)
			t = N+2;
		else if ((X-D)/L>=N)
			t = N-1;
		else
			t = (X-D)/L;
		if (t<N) {
			q = new nod;
			q->inf = A;
			q->adr = T[t];
			T[t] = q;
		}
	}
	fclose(f);
	
	for (i=N-1;i>=0;i--) {
		q = T[i];
		while (q) {
			baga(q->inf);
			q = q->adr;
		}
		if (dH!=0) {
			S+=H[1];
			scoate();
		}
	}
	
	FILE *g = fopen("lupu.out","w");
	fprintf(g,"%d",S);
	fclose(g);
	return 0;
}