Pagini recente » Profil Lagadinoses90a | Cod sursa (job #3123815) | Eu Romania | Borderou de evaluare (job #3209947) | Cod sursa (job #441018)
Cod sursa(job #441018)
#include<stdio.h>
#define min(i, x) (((i) < (x))?(i):(x))
int i, j, N, H, U, tN;
int h[100000], g[100000], t[100000];
//h - inaltimile gutuilor, g - greutatile
//t[i] - greutatea maxima care se poate obtine la momentul de timp i;
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;
}
int partitie(int left, int right){
int i, j, x = h[left];
i = left;
for(j = left + 1; j <= right; j++)
if(h[j] > x){
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);
for(i = 0; i < N; i++){
scanf("%d", &h[i]);
scanf("%d", &g[i]);
}
//se sorteaza gutuile in ordine descrescatoare dupa inaltime
//(la inceput, cele care se pierd cel mai devreme)
qsort(0, N);
t[1] = g[0];
//tmin = de cate ori se poate ridica, maxim, gutuiul, p?n? ?n momentul prezent
int x, max = g[0], minim, tmin = 1;
for( i = 1; i < N; i++){ //parcurg gutuile
x = (H - h[i]) / U; //la al catelea moment de timp, pierd gutuia i.
minim = min(x, tmin);
for( j = minim + 1; j >= 1; j--)
// parcurg toate momentele de timp anterioare
if((t[j - 1] + g[i]) > t[j]){
/*daca la momentul j, culeg gutuia i si obtin o
greutate mai buna decat cea precedenta, atunci o retin
ca fiind cea mai buna solutie partiala, pana la momentul j*/
t[j] = t[j - 1] + g[i];
if(t[j] > max)// daca e cea mai buna solutie gasita
max = t[j];
if(j == minim + 1) // daca am putut lega gutuia i de cel
//mai mare moment de timp, atunci incrementez tmin.
tmin ++;
}
}
//se afiseaza maximul
printf("%d", max);
getchar();
getchar();
return 0;
}