Pagini recente » Cod sursa (job #440241) | Cod sursa (job #2590554) | Cod sursa (job #2711094) | Cod sursa (job #507747) | Cod sursa (job #435312)
Cod sursa(job #435312)
/*
* File: Problema2.c
* Author: Bosilca Adrian 325CC
*
*/
#include <stdio.h>
#include <stdlib.h>
int u;
typedef struct gutuie{
int h;
int g;
}gutuie;
void afisare(gutuie v[], int n) {
int i;
for (i = 0 ; i < n ; i++) {
printf("%d %d\n", v[i].g, v[i].h);
}
printf("\n");
}
int comp(const void* a, const void* b) {
gutuie *c = (gutuie*)a;
gutuie *d = (gutuie*)b;
return ( d->g - c->g );
}
int main() {
FILE* f = fopen("gutui.in", "r");
int n, h, i, j, dif, k = 0, s = 0;
gutuie v[100000], aux;
int best[100000];
fscanf(f, "%d %d %d", &n, &h, &u); //citirea datelor de intrare
for (i = 0 ; i < n ; i++) {
fscanf(f, "%d %d", &v[i].h, &v[i].g);
}
fclose(f);
qsort(v, n, sizeof(gutuie), comp);
for (i = 0 ; i < n, k < n; k++) {
dif = i*u;
//printf("v[%d].h = %d\n", i, v[i].h);
if (v[i].h+dif+u <= h) {
aux = v[i];
dif = dif + u;
//printf("aux =%d dif =%d\n", aux.h, dif);
for (j = i ; aux.h+dif <= h ; j++) {
v[j] = v[j+1];
// afisare(v, n);
dif = dif + u;
}
v[j] = aux;
}
dif = i*u;
if (v[i].h+dif+u > h)
i++;
}
//afisare(v, n);
for (i = 0 ; i <n ; i++) {
dif = i*u;
if (v[i].h + dif <= h)
s = s + v[i].g;
else
break;
}
/*for (i = 0 ; i < n ; i++) {
best[i] = 0;
dif = 0;
for (j = i ; j < n; j++)
if (v[j].h+dif <= h) {
best[i] += v[j].g;
dif += u;
}
}
for (i = 0 ; i < n ; i++)
printf("%d ", best[i]);
for (i = 0 ; i < n ; i++)
if (max < best[i])
max = best[i];*/
f = fopen("gutui.out", "w");
fprintf(f, "%d", s);
fclose(f);
return 0;
}