Cod sursa(job #435172)

Utilizator RaphyRafailescu Marius Raphy Data 6 aprilie 2010 23:34:35
Problema Gutui Scor 40
Compilator cpp Status done
Runda teme_upb Marime 3.14 kb
#include <stdio.h>  
#include <stdlib.h>  
#include <fstream>

using namespace std;
typedef struct {
	int h;
	int g;
}gutuie;

void merge(int starts,int startd,int stopd,gutuie *a){  
	int n=stopd-starts+1;  
	int is=starts,id=startd,stops=startd-1,it=0,i;  
	gutuie *temp=(gutuie*)malloc(n*sizeof(gutuie));  
   
	while(is<=stops && id<=stopd) { 
		if (a[is].h<a[id].h){
			temp[it].h=a[is].h;
			temp[it++].g=a[is++].g;
		}
		else if (a[is].h > a[id].h){
			temp[it].h=a[id].h;
			temp[it++].g=a[id++].g;
		}  else{ //egale
			if (a[is].g < a[id].g){
				temp[it].h=a[is].h;
				temp[it++].g=a[is++].g;
			}
			else {
				temp[it].h=a[id].h;
				temp[it++].g=a[id++].g;
			}
		}
	}
	while (is<=stops){
		temp[it].h=a[is].h;
		temp[it++].g=a[is++].g;
	}
	while (id<=stopd){
		temp[it].h=a[id].h;
		temp[it++].g=a[id++].g;
	}   
	  
	for (i=0;i<n;i++){
		a[starts+i].h=temp[i].h;
		a[starts+i].g=temp[i].g;
	}
	free(temp);  
}  
   
void MS(int s,int d,gutuie *a){  
if (s<d)  
    {  
    int m=(s+d)/2;  
    MS(s,m,a);  
    MS(m+1,d,a);  
    merge(s,m+1,d,a);  
    }  
}  
  
void MergeSort(int n,gutuie *a){  
    MS(0,n-1,a);  
}

int pcmpa(int *v, int n){
	int minim,p,c;
	minim=v[0];p=0;
	for (c=1;c<n;++c){
		if (minim == 0) return p;
		if (v[c]<minim){
			minim=v[c];
			p = c;
		}
	}
	return p;
}  
   
int main(){  
int n,h,u,i,max=0,j,*best,*sbest,ch,k,niv=0,poz;  
ifstream in("gutui.in");
ofstream out("gutui.out");  
//ofstream test("test.txt");
in >> n; in >> h; in >> u;
gutuie *v=(gutuie*)calloc(n,sizeof(gutuie));
best=(int*)calloc(h/u+2,sizeof(int)); 
sbest=(int*)calloc(u+1,sizeof(int)); 
for (i=0;i<n;++i){
	in >> v[i].h; 
	in >> v[i].g;
	//total+=v[i].g;
}
MergeSort(n,v); 
//test << "Se pot lua maxim "<<total<<"kg de gutui\n";
//test << "Gutuile sortate\n";
//for (i=n-1;i>=0;i--)
//	test << "N=" << i<<":" <<v[i].h << " " << v[i].g << endl;

while (niv<=h/u){
	k=0;
	//test << "Acum incep cu niv=" << niv << endl;
	max=0;
	ch=0;
	sbest=(int*)calloc(u+1,sizeof(int)); 
	for (j=n-1;j>=0;--j){
		//test << "testez daca v[" << j <<"].h=" << v[j].h<<" e in intervalul ("<<h-niv*u<<","<<h-(niv+1)*u+1<<endl; 
		if (v[j].h <= h-niv*u) 		
		{
			if (v[j].h >= h-(niv+1)*u+1)// dc e cuprins in nivelul curent
			{
				if (max<v[j].g) {
					max=v[j].g;
					if (best[niv]==0) best[niv]=max;
					else{
						sbest[ch++]=best[niv];
						best[niv]=max;
					}
			
				}
				else{
					sbest[ch++]=v[j].g;
				}
			}
			else break;
		}
	}

	
	if (ch) poz=pcmpa(best,niv);//test<<"Cea mai proasta alegere e "<< best[poz]<<"pe poz="<<poz<<endl;}
	for (i=0;i<ch && k<niv;i++){
		if (sbest[i]>best[poz]){
			best[poz]=sbest[i];
			//test<<"Am gasit o imbunatatire si best["<<poz<<"]="<<best[poz]<<endl;
			++k;
			if (i!=ch-1) poz = pcmpa(best,niv);
		}
	}
	//test << "La nivelul "<< niv <<" am best\n";
	//for (i=0;i<=niv;i++)
	//	test << best[i] << " ";
	//test << endl;
	++niv;
}

max=best[0];
//printf("max=%d\n",max);
for (i=1;i<niv;i++) max+=best[i];//printf("max=%d\n",max);}

out << max;
free(v);
free(best);
free(sbest);
in.close();  
out.close();  
//test.close();
return 0;  
}