Pagini recente » Cod sursa (job #775628) | Cod sursa (job #1800799) | Cod sursa (job #227383) | Cod sursa (job #2943601) | Cod sursa (job #426927)
Cod sursa(job #426927)
/*
N - numar de gutui din copac
H - inaltimea maxima la care ajunge Gigel
U - cu cat se ridica crengile dupa ridicarea unei gutui
*/
#include<stdio.h>
#include<stdlib.h>
#define MAX 100000
struct pair
{
int inaltime;
int greutate;
};
void merge(struct pair *vector, int start, int middle, int end)
{
int i,j;
int n = middle - start + 1;
int m = end - middle;
struct pair *left = (struct pair *)calloc(n, sizeof(struct pair)); //parcurs cu i
struct pair *right = (struct pair *)calloc(m, sizeof(struct pair)); //parcurs cu j
//copiez elementele
for (i=0;i<n;i++)
left[i] = vector[start+i];
for (i=0;i<m;i++)
right[i] = vector[middle +1 +i];
i = 0;
j = 0;
int k = start;
while (i<n && j<m)
{
if (left[i].inaltime < right[j].inaltime)
vector[k++] = left[i++];
else
vector[k++] = right[j++];
}
while (i<n)
vector[k++] = left[i++];
while (j<m)
vector[k++] = right[j++];
free(left);
free(right);
}
void mergeSort(struct pair *vector, int start, int end)
{
int middle;
if (start < end)
{
middle = (start+end)/2;
mergeSort(vector, start, middle);
mergeSort(vector, middle+1, end);
merge(vector, start, middle, end);
}
}
int enabled[MAX];
int main()
{
FILE *in = fopen("gutui.in", "r");
FILE *out = fopen("gutui.out", "w");
struct pair p[MAX];
int n, h, u, i, k=0;
int temp_h, temp_g;
fscanf(in, "%d%d%d", &n, &h, &u);
for (i=0; i<n; i++){
fscanf(in, "%d%d", &temp_h, &temp_g);
if (temp_h<=h)
{
p[k].inaltime=temp_h;
p[k].greutate=temp_g;
k++;
}
}
n = k; //!! aici raman doar la gutuile la care pot ajunge
/*
printf("\n-------------\n");
for (i=0;i<n;i++)
printf("[%d %d] ",p[i].inaltime, p[i].greutate);
*/
mergeSort(p, 0, n-1);
/*
printf("\n");
for (i=0;i <n; i++)
printf("[%d %d] ",p[i].inaltime, p[i].greutate);
printf("\n-------------\n\n");
*/
//rezolvare
int greutateMaxima=0, min,j;
int addedHeight=0, minhelper;
min=p[n-1].greutate;
for (i=n-1;i>=0;i--)
{
if (p[i].inaltime+addedHeight<=h)
{
enabled[i]=1;
greutateMaxima += p[i].greutate;
addedHeight+=u; //actualizez addedHeight
//actualizez min daca este nevoie
if (p[i].greutate < min)
min = p[i].greutate;
}
else
{
//nu modific addedHeight
//vad daca e mai mare decat minimul solutiei anterioare
if (p[i].greutate > min)
{
//atunci inseamna ca trebuie adaugat
greutateMaxima -= min;
greutateMaxima += p[i].greutate;
enabled[i] = 1;
//actualizez minim
for (j=i+1;j<n;j++)
if (enabled[j]==1&&p[j].greutate==min)
{enabled[j] = 0;break;}
minhelper=p[i].greutate;
for (j=i+1;j<n;j++)
if (enabled[j] && p[j].greutate<minhelper
&& p[j].greutate >=min)
minhelper = p[j].greutate;
min=minhelper;
}
}
}
//afisez la ecran
//printf("\ngreutate: %d\n", greutateMaxima);
//printf("\n");
//for (i=n-1;i>=0;i--)
//printf("%d ",enabled[i]);
fprintf(out,"%d",greutateMaxima);
//EXIT
fclose(in);
fclose(out);
return 0;
}