Cod sursa(job #440304)

Utilizator encyEnciu Bogdan ency Data 11 aprilie 2010 23:39:02
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 3.04 kb
#include <stdio.h>
#include <stdlib.h>
int sort1(const void *x, const void *y) {      //functie de comparare pt sortare
      return (*(int*)y - *(int*)x);            //sortare descrescatoare
}
void sorta2(unsigned long int a[][2],unsigned long int n){     // apelare qsort pt a 
	qsort(a,n,sizeof(unsigned long int[2]),sort1);
}

void add (unsigned long int a[],unsigned long int gr,unsigned long int t,unsigned long int &r){ //functie de adaugare  in vector ordonat crescator
	if(r==t)  {   			//inserare initiala						
		a[t]=gr;
		r++;
		return;
	}
	if(gr<=a[t]) {				//la inceput 
		for(int i=r;i>t;i--) 
 			a[i]=a[i-1];
		a[t]=gr;
		r++;
		return;
 	}
	if(gr>=a[r-1]) {			//la sfarsit
		a[r]=gr;
		r++;
		return;
 	}
	for(int i=t;i<r;i++)			  //inserare intre doua elemente
		if(a[i]<=gr&&gr<=a[i+1]) {
			for(int j=r;j>i+1;j--) 
 				a[j]=a[j-1];
			a[i+1]=gr;
			r++;
			return;
			}
}
unsigned long int gutui(unsigned long int c[][2],unsigned long int n,unsigned long int h,unsigned long int u){ //functia care calculeaza greutatea optima
	unsigned long int i,k=0,m=0;                     //i index  , k  pasul la care ne aflam pe inaltime , m  masa  
	unsigned long int *a;                            // vector ce va fi ordonat si ajuta la calcularea greutatii optime  
	unsigned long int t=0,r=0;                         //t = index de inceput si r = sfarsit al vectorului ordonat
	a=(unsigned long int *)malloc(n*sizeof(unsigned long int));
	if(u>=h) {						
		for(i=0;i<n;i++)
			if(m<c[i][1]&&c[i][0]<=h)		// daca se poate lua un singura gutuie o luam pe cea maxima si iesim
				m=c[i][1];
		return m; }
	for(i=0;i<n;i++) 					//gutuile ce depasesc inaltimea maxima nu se pot lua O(n) 
		if(c[i][0]>h)  {
			c[i][0]=0;c[i][1]=0;
		}					
	sorta2(c,n); 					        //se sorteaza descrescator dupa inaltime  O(n*log(n)) 
	for(i=0;i<n;i++)					//pt fiecare gutuie
		
		if(k<=h-c[i][0])  {                             //se compara cu pasul curent pasul gutui h - inaltimea gutui  
				m=m+c[i][1];                    // daca este mai mic se adauga la masa si in vectorul sortat 
				add(a,c[i][1],t,r);		
				k=k+u;				//pasul curent creste cu u
				}
			else  if(c[i][1]>a[t])                  // daca gutuia nu se afla la pasul curent dar e mai grea decat minimul din vector  
									
				         { 
					   m=m-a[t];		//se elimina din vector si din suma minimul 
				          t++; 	           
					  m=m+c[i][1];          //se adauga  in vector si  suma greutatea noii gutui 
					   add(a,c[i][1],t,r);   
					}    				
				
			return m;				//se returneaza masa 
}
int main(){
	 unsigned long int c[100000][2];                        //vectorul de gutui  inaltimi/greutati 
	 unsigned long int i,n,h,gr,u;                          
         freopen("gutui.in", "r", stdin);			
         freopen("gutui.out", "w", stdout); 
         scanf("%ld",&n);					//se citesc n ,h,u si gutuile cu greutatiile si inaltimile
	 scanf("%ld",&h);
	 scanf("%ld",&u);
 	 for (i=0;i<n;i++) { 
     	 		scanf("%ld",&c[i][0]); 
			scanf("%ld",&c[i][1]);
	}
	gr=gutui(c,n,h,u);
	printf("%ld\n",gr);
	return 0;
}