Pagini recente » Cod sursa (job #1080646) | Cod sursa (job #1138680) | Cod sursa (job #1724575) | Cod sursa (job #14809) | Cod sursa (job #438461)
Cod sursa(job #438461)
#include <stdio.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAXX 100001
typedef struct DATE {
unsigned long int a;
unsigned long int b;
} date;
date in[MAXX];
date out[MAXX];
void merge(int low, int high, int mid) {
int i, j, k;
unsigned long int c[MAXX],d[MAXX];
i=low;
j=mid+1;
k=low;
while((i<=mid)&&(j<=high)) {
if (in[i].a > in[j].a) {
c[k]=in[i].a;
d[k]=in[i].b;
k++;
i++;
}
else {
c[k]=in[j].a;
d[k]=in[j].b;
k++;
j++;
}
}
while(i <= mid) {
c[k]=in[i].a;
d[k]=in[i].b;
k++;
i++;
}
while(j<=high){
c[k]=in[j].a;
d[k]=in[j].b;
k++;
j++;
}
for(i=low;i<k;i++) {
in[i].a=c[i];
in[i].b=d[i];
}
}
void mergesort( int low, int high) {
int mid;
if(low<high) {
mid=(low+high)/2;
mergesort(low,mid);
mergesort(mid+1,high);
merge(low,high,mid);
}
}
int main () {
FILE *f,*g;
f=fopen("gutui.in","r");
g=fopen("gutui.out","w");
unsigned long int n,h,u;
fscanf (f, "%lu %lu %lu",&n,&h,&u);
char c[100];
fgets(c,MAXX,f); // sa ajung pe urm linie
int i,j;
unsigned long int gmax=0; // greutatea maxima
for (i=0;i<n;i++)
fscanf (f, "%lu %lu",&in[i].a,&in[i].b);
mergesort(0,n-1);
int k = 0; //contor pt a numara cate elem voi avea in out
for (i = 0; i < n;i ++ )
if (in[i].a <= h) {
out[k].a = in[i].a;
out[k].b = in[i].b;
gmax += in[i].b;
h -= u ;
k++;
}
else {
int pozmin=0;
for (j=1;j<k;j++) {
if (out[j].b < out[pozmin].b )
pozmin=j;
}
if (k !=0)
if ( in[i].b > out[pozmin].b ) {
gmax =gmax + in[i].b - out[pozmin].b;
out[pozmin].a = in[i].a;
out[pozmin].b = in[i].b;
}
}
fprintf(g, "%lu\n",gmax);
return 0;
}