Pagini recente » Cod sursa (job #1106930) | Cod sursa (job #2078822) | Cod sursa (job #116362) | Cod sursa (job #617682) | Cod sursa (job #435103)
Cod sursa(job #435103)
#include<stdio.h>
#define min(i, x) (((i) < (x))?(i):(x))
int i, j, N, H, U;
//int *h, *g, *sol;
int h[100], g[100], sol[100];
//h - inaltimile gutuilor, g - greutatile
//t[i] - greutatea maxima care se poate obtine la momentul de timp i;
//functie de interschimbare
void swap(int i, int j){
int aux = h[i];
h[i] = h[j];
h[j] = aux;
aux = g[i];
g[i] = g[j];
g[j] = aux;
}
//pozitioneaza pivotul de pe prima pozitie a.i.
//in stanga sunt toate elementele mai mici decat el
//in dreapta, toate elementele mai mari decat el
int partitie(int left, int right){
int i, j, x = (H - h[left])/U;
i = left;
for(j = left + 1; j <= right; j++)
if((H - h[j])/U < x || ((H-h[j])/U == x && g[j] > g[left])){
i = i + 1;
swap(i, j);
}
swap(left, i);
return i;
}
void qsort(int left, int right){
if(left >= right)
return;
int poz = partitie(left, right);
qsort(left, poz - 1);
qsort(poz + 1, right);
}
int main(){
freopen("gutui.in","r", stdin);
freopen("gutui.out","w",stdout);
int i;
//citire
scanf("%d%d%d", &N, &H, &U);
/*h = (int *)calloc(N + 1, sizeof(int));
g = (int *)calloc(N + 1, sizeof(int));
sol = (int *)calloc(N + 1, sizeof(int)); */
for(i = 0; i < N; i++){
scanf("%d", &h[i]);
scanf("%d", &g[i]);
}
//se sorteaza gutuile in ordine crescatoare dupa momentul de timp la care
//le PIERD
qsort(0, N);
int t = 0, x, max = 0;
for(i = 0; i < N && H - h[i] < 0; i++);
for(; i < N; i++)
for(j = min(t, (H - h[i])/U); j >= 0; j--)
if(g[i] + sol[j] > sol[j+1]){
if(j == t)
t++;
sol[j+1] = g[i] + sol[j];
if(sol[j+1]>max)
max = sol[j+1];
}
else
break;
//se afiseaza maximul
printf("%d", max);
return 0;
}