Pagini recente » Cod sursa (job #1789686) | Cod sursa (job #2398358) | Cod sursa (job #2658867) | Cod sursa (job #1119871) | Cod sursa (job #438865)
Cod sursa(job #438865)
#include <stdio.h>
#include <stdlib.h>
//sortare quickSort dupa un vector a
void quickSort (int a[],int b[], int l, int r) {
int i = l, j = r, aux, m;
m = a[( l + r ) / 2];
while (i <= j) {
while ( a[i] > m )
i++;
while ( a[j] < m )
j--;
if ( i <= j ) {
aux = a[i]; a[i] = a[j]; a[j] = aux;
aux = b[i]; b[i] = b[j]; b[j] = aux;
i++; j--;
}
}
if ( l < j )
quickSort(a, b, l, j);
if ( i < r )
quickSort(a, b, i, r);
}
int main() {
int N, H, U, h[100000], g[100000], i, s = 0, j, m[100000], x, max;
FILE *f1, *f2;
f1 = fopen ("gutui.in", "r");
f2 = fopen ("gutui.out", "w");
fscanf(f1, "%d", &N);
fscanf(f1, "%d", &H);
fscanf(f1, "%d", &U);
for ( i = 0; i < N; i++) {
fscanf(f1, "%d", &h[i]);
fscanf(f1, "%d", &g[i]);
}
//sortare dupa greutate
quickSort(g, h, 0, N);
//m este un vector care poate lua valoarea 0 sau 1
//1 - daca indicele lui m este un pas luat de o inaltime
//0 - daca indicele lui m este un pas disponibil
m[( H - h[0] ) / U + 1] = 1;
s = g[0];
for ( i = 1; i < N; i++){
x = ( H - h[i] ) / U + 1; // pasul la care poate culege gutuia cel mai tarziu
max = 0;
for ( j = x; j > 0; j--) // se verifica daca pasul respectiv este ocupat de alta inaltime
if ( m[j] == 0 ) // daca da inaltimii corespunzatoare i se atribuie cel mai mare pas mai mic
if ( j > max ) // decat el disponibil
max = j;
if ( max > 0 ) // daca gutuia de la inaltimea h[i] poate fi culeasa la un anumit pas, greutatea
s = s + g[i]; // ei se adauga la suma totala
m[max] = 1; // pasul atribuit inaltimii este marcat cu 1, deci devine nedisponibil
}
fprintf(f2, "%d", s);
fclose(f1);
fclose(f2);
return 0;
}