Pagini recente » Cod sursa (job #2529466) | Cod sursa (job #2395482) | Cod sursa (job #492565) | Cod sursa (job #235431) | Cod sursa (job #422638)
Cod sursa(job #422638)
#include <stdio.h>
#include <stdlib.h>
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 main(){
int n,h,u,i,max=0,j,best;
FILE *in,*out;
in=fopen("gutui.in","rt");
out=fopen("gutui.out","wt");
fscanf(in,"%d%d%d",&n,&h,&u);
gutuie *v=(gutuie*)calloc(n,sizeof(gutuie));
for (i=0;i<n;++i)
fscanf(in,"%d%d",&v[i].h,&v[i].g);
MergeSort(n,v);
j=n-1;
for (i=j;i>=0;--i){
//printf("i=%d ",i);
if (v[i].h<=h){
max+=v[i].g;
h-=u;
}
}
fprintf(out,"%d\n",max);
free(v);
fclose(in);
fclose(out);
return 0;
}