Pagini recente » Cod sursa (job #2463117) | Cod sursa (job #2300827) | Cod sursa (job #1510292) | Cod sursa (job #3175003) | Cod sursa (job #422706)
Cod sursa(job #422706)
#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,total=0,ch;
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));
best=(int*)calloc(n,sizeof(int));
for (i=0;i<n;++i){
fscanf(in,"%d%d",&v[i].h,&v[i].g);
total+=v[i].g;
}
MergeSort(n,v);
for (j=0;j<n;j++){
ch=h;
max=0;
for (i=n-1-j;i>=0;--i){
if (v[i].h<=ch){
max+=v[i].g;
ch-=u;
}
}
best[j]=max;
if (max == total) break;
}
max=best[0];
for (i=1;i<n;i++)
if (best[i]>max) max=best[i];
fprintf(out,"%d",max);
free(v);
free(best);
fclose(in);
fclose(out);
return 0;
}