Pagini recente » Cod sursa (job #1359217) | Cod sursa (job #2704819) | Cod sursa (job #2075020) | Cod sursa (job #502629) | Cod sursa (job #463560)
Cod sursa(job #463560)
// Sasu Vitalie 323CA
#include <stdio.h>
#include <stdlib.h>
// sortez vectorii cu quicksort
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);
}
// gasesc nivelul pe care se afla gutuia
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;
// creez un vector auxiliar de lungime h/u
// pe care il initializez cu nr de gutuie pe care le pot culege de pe nivele
// Ex: de pe nivelul (0, h] pot culege nrLevel gutui
// pe cand de pe (h-u, h] doar o singura gutuie
aux = (long*)malloc (nrLevel * sizeof (long));
for (i = 0; i < nrLevel; i++)
{
aux[i] = temp;
temp--;
}
tempNrLevel = nrLevel;
i = 0;
do
{
// verific daca initial pot accesa gutuia
if (high[i] > h)
{
i++;
continue;
}
// verific daca exista vreo gutuie la inaltimea 0
if (high[i] == 0)
{
if (zero == 0)
{
zero++;
tempNrLevel++;
}
// printf("Culeg gutuia\n");
nrGutui++;
gmax += wheight[i];
i++;
continue;
}
// aflu pe ce nivel se afla gutuia pe care o culeg
// verific de la nivele cele mai mici spre cele mari
// Ex: (h-u, h] .. (0, h]
level = getLevel (high[i], h, u, nrLevel - 1);
// verific daca o pot culege
if (aux[level] > 0)
{
// daca culeg o gutuie
// scad nr de gutui pe care le pot culege de pe nivelele inferioare
while (level >= 0)
{
aux[level]--;
// daca am cules toate gutuile de pe un nivel
// atunci nu mai pot culege nici o gutuie de pe nivelele superioare
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;
}