Cod sursa(job #441582)

Utilizator BrEacKRazvan Aurariu BrEacK Data 12 aprilie 2010 23:24:49
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 4.28 kb
#include<stdio.h>
#include<stdlib.h>

typedef struct Gutuie{
	int gr;
	struct Gutuie* prec;
	struct Gutuie* urm;
}gutuie;

typedef struct Pas{
	int nr;
	int luate;
	struct Gutuie* first;
	struct Pas* urm;
	struct Pas* prec;
}pas;

//#define DEBUG 1
int main(int argc, char* argv[]) {
	FILE * fin = fopen("gutui.in","r");
	FILE * fout = fopen("gutui.out","w");

	stdin = fin;
	stdout = fout;

	pas pasi;
	pasi.nr = -1;
	pasi.prec = NULL;
	pasi.urm = NULL;
	pasi.first = NULL;
	pas* ppas, *tmp_ppas = NULL;
	gutuie *pgutuie, *tmp_pgutuie;
	int i, j;
	int n, h, u;
	int inaltime, greutate, nr_pasi_max, start, nr_pas, rezolvat, luate, max_gutui, nivel_minim = ~(1 << 31), nivel_maxim_cautare;
	int t_max_gr, t_max_pas;

	fscanf(stdin,"%d %d %d\n",&n, &h, &u);
	h++;
	nr_pasi_max = (h-1)/u + !(!((h-1)%u));

	start = h%u;

	for(i = 0;i < n; i++) {
		fscanf(stdin,"%d %d\n",&inaltime,&greutate);
		if(inaltime < h) {
			nr_pas = (inaltime - start) / u;
			tmp_pgutuie = (gutuie*)malloc(sizeof(gutuie));
			tmp_pgutuie->gr = greutate;
			tmp_pgutuie->prec = NULL;
			tmp_pgutuie->urm = NULL;
			ppas = &pasi;
			rezolvat = 0;
			while(ppas != NULL && !rezolvat) {
				if(nr_pas == ppas->nr) {
					pgutuie = ppas->first;
					if(ppas->first == NULL) {
						if(nivel_minim > nr_pas) {
							nivel_minim = nr_pas;
						}
						ppas->urm->first = tmp_pgutuie;
						rezolvat = 1;
					}else {
						j = 0;
						while(pgutuie != NULL && (pgutuie->gr >= greutate) && !rezolvat) {
							if((pgutuie->urm != NULL) && (pgutuie->urm->gr <= greutate)) {
								tmp_pgutuie->prec = pgutuie;
								tmp_pgutuie->urm = pgutuie->urm;
								pgutuie->urm->prec = tmp_pgutuie;
								pgutuie->urm = tmp_pgutuie;
								rezolvat = 1;
							} else if(pgutuie->urm == NULL) {
								pgutuie->urm = tmp_pgutuie;
								pgutuie->urm->prec = pgutuie;
								rezolvat = 1;
							}
							pgutuie = pgutuie->urm;j++;
						}
						if(pgutuie != NULL && (pgutuie->gr < greutate)) {
							tmp_pgutuie->urm = ppas->first;
							ppas->first = tmp_pgutuie;
							rezolvat = 1;
						}
					}
				} else if((nr_pas > ppas->nr) && (ppas->urm != NULL) && (nr_pas < ppas->urm->nr)) {
					tmp_ppas = ppas->urm;
					ppas->urm = (pas*)malloc(sizeof(pas));
					ppas->urm->nr = nr_pas;
					ppas->urm->prec = ppas;
					ppas->urm->urm = tmp_ppas;
					ppas->urm->first = tmp_pgutuie;
					if(nivel_minim > nr_pas) {
						nivel_minim = nr_pas;
					}
					rezolvat = 1;
				} else if((nr_pas > ppas->nr) && (ppas->urm == NULL)) {
					tmp_ppas = NULL;
					ppas->urm = (pas*)malloc(sizeof(pas));
					ppas->urm->nr = nr_pas;
					ppas->urm->prec = ppas;
					ppas->urm->urm = tmp_ppas;
					ppas->urm->first = tmp_pgutuie;
					if(nivel_minim > nr_pas) {
						nivel_minim = nr_pas;
					}
					rezolvat = 1;
				}
				ppas = ppas->urm;
			}
		}
	}

	max_gutui = (nr_pasi_max - nivel_minim) < 100000 ?(nr_pasi_max - nivel_minim) : 100000 ;
	luate = 0;
	greutate = 0;
	rezolvat = 0;
	nivel_maxim_cautare = nivel_minim;
	greutate = 0;
	j = 0;

	while((j < max_gutui)&&(max_gutui - luate)) {
		ppas = pasi.urm;
		t_max_gr = -1;
		tmp_ppas = NULL;
		//fprintf(stderr, "Incep sa caut cu %d\n",ppas->nr);
		while((ppas != NULL) && (nivel_maxim_cautare  >= ppas->nr)) {
			if(ppas->nr >= nivel_minim) {
				//fprintf(stderr, "Verific %d < %d|", t_max_gr , ppas->first->gr);
				if(ppas->first != NULL && ppas->first->gr > t_max_gr && (ppas->luate < (nr_pasi_max-ppas->nr))) {
					t_max_gr = ppas->first->gr;
					t_max_pas = ppas->nr;
					tmp_ppas = ppas;
				}
			}

			ppas = ppas->urm;
		}
		//fprintf(stderr, "Am cautat gutuia si am gasit? %d\n", (tmp_ppas != NULL));
		j++;
		nivel_maxim_cautare = nivel_minim+j;
		if(tmp_ppas != NULL) {
			luate++;
			tmp_ppas->luate++;
			greutate += tmp_ppas->first->gr;
			tmp_pgutuie = tmp_ppas->first;
			tmp_ppas->first = tmp_pgutuie->urm;
			/*if(tmp_ppas->first == NULL && 0) {
				//fprintf(stderr, "Trebuie eliminat nivelul %d\n", tmp_ppas->nr);

				if(tmp_ppas->urm != NULL) {
					tmp_ppas->urm->prec = tmp_ppas->prec;
				}
				tmp_ppas->prec->urm = tmp_ppas->urm;

			}*/
		}
		//fprintf(stderr, "Am luat: %d de pe %d\nNoile date sunt:nivel_maxim=%d nivel_minim=%d j=%d\n",tmp_pgutuie->gr,tmp_ppas->nr,nivel_maxim_cautare,nivel_minim,j);
	}

	//fprintf(stderr,"%d\n",greutate);
	fprintf(fout,"%d\n",greutate);
	fclose(fin);
	fclose(fout);
	return 0;
}