Pagini recente » Cod sursa (job #2215916) | Cod sursa (job #566519) | Cod sursa (job #1004639) | Cod sursa (job #140123) | Cod sursa (job #441067)
Cod sursa(job #441067)
#include <stdio.h>
#include <stdlib.h>
void swap (long *vec, long n, long poz)
{
long aux;
aux = vec[n - 1];
vec[n - 1] = vec[poz];
vec[poz] = aux;
}
void quicksort (long *high, long *wheight, long left, long right)
{
long i = left;
long j = right;
long aux;
long x = wheight[left];
do
{
while (wheight[i] > x) i++;
while (wheight[j] < x) j--;
if (i<=j)
{
aux = wheight[i]; wheight[i] = wheight[j]; wheight[j] = aux;
aux = high[i]; high[i] = high[j]; high[j] = aux;
i++; j--;
}
} while (i <= j);
if (left < j) quicksort(high, wheight, left, j);
if (i < right) quicksort(high, wheight, i, right);
}
long getLevel (long x, long h, long u, long nr)
{
h -= u;
while (x <= h)
{
nr--;
h -= u;
}
return nr;
}
int main ()
{
long n, h, u, i, temp;
long *high, *wheight, *aux;
FILE *fin, *fout;
long nrLevel = 0;
long gmax = 0;
long level, tempNrLevel, nrGutui = 0;
int zero = 0;
fin = fopen ("gutui.in", "r");
if (fin == NULL)
{
printf("reading error!\n");
exit(0);
}
fout = fopen ("gutui.out", "w");
fscanf(fin, "%ld %ld %ld", &n, &h, &u);
high = (long*)malloc (n * sizeof (long));
wheight = (long*)malloc (n * sizeof (long));
for (i = 0; i < n; i++)
{
fscanf(fin, "%ld %ld", &high[i], &wheight[i]);
}
// sortez gutuile dupa greutate
quicksort (high, wheight, 0, n-1);
// temp = h;
// cate gutuie maxim pot culege
// while (temp > 0)
// {
// temp -= u;
// nrLevel++;
// }
temp = nrLevel = h/u;
// creez un vector auxiliar de lungime
//
aux = (long*)malloc (nrLevel * sizeof (long));
for (i = 0; i < nrLevel; i++)
{
aux[i] = temp;
temp--;
}
tempNrLevel = nrLevel;
i = 0;
do
{
if (high[i] > h)
{
i++;
continue;
}
if (high[i] == 0)
{
if (zero == 0)
{
zero++;
tempNrLevel++;
}
// printf("Culeg gutuia\n");
nrGutui++;
gmax += wheight[i];
i++;
continue;
}
level = getLevel (high[i], h, u, nrLevel - 1);
// culeg gutuia
if (aux[level] > 0)
{
while (level >= 0)
{
aux[level]--;
if (aux[level] == 0)
{
temp = level;
while (temp < nrLevel)
{
aux[temp] = 0;
temp++;
}
}
level--;
}
gmax += wheight[i];
nrGutui++;
}
i++;
}while (i < n && nrGutui < tempNrLevel);
fprintf(fout, "%ld\n", gmax);
return 0;
}