Pagini recente » Cod sursa (job #1529802) | Cod sursa (job #1038050) | Cod sursa (job #3004995) | Cod sursa (job #545595) | Cod sursa (job #438762)
Cod sursa(job #438762)
#include <fstream>
#include <stdlib.h>
using namespace std;
struct gutuie {
int g; // greutatea
int n; // nr max de gutui culese anterior pt care gutuia ramane accesibila, numit "nivel"
int idx; // indexul
};
#define S (sizeof(gutuie))
ifstream in ("gutui.in");
ofstream out("gutui.out");
int n, h, u, r = 0, nr = 0, *del;
gutuie *gutui, *gutui2;
// comparara dupa nivel
int cmp_n(const void* fp1, const void* fp2) {
gutuie* f1 = (gutuie*)fp1;
gutuie* f2 = (gutuie*)fp2;
int r = f1->n - f2->n;
return (r == 0 ? f2->g - f1->g : r);
}
// comparara dupa greutate
int cmp_g(const void* fp1, const void* fp2) {
gutuie* f1 = (gutuie*)fp1;
gutuie* f2 = (gutuie*)fp2;
int r = f1->g - f2->g;
return (r == 0 ? f1->n - f2->n : r);
}
void print() {
for (int i = 0; i < n; i++) {
printf("%9d %d %d %9d %d %d\n", gutui[i].g, gutui[i].n, gutui[i].idx, gutui2[i].g, gutui2[i].n, gutui2[i].idx);
}
printf("\n");
}
int main() {
in >> n >> h >> u;
gutui = new gutuie[n];
int ch, cg, cn, cnr, i, j, k, rem;
/***********************************************************************************************************
* - citire din fisier
* - o prima selectie - selectatrea cazurilor convenabile, adica
* eliminarea gutuilor la care nu se poate ajunge din prima , adica nivelul < 0 si
* a celor cu greutate nula (daca exista)
* - nr gutuilor ramase dupa aceasta prima selectie fiind nr <= n
*
***********************************************************************************************************/
r = 0;
for (i = 0; i < n; i++) {
in >> ch >> cg; // citire inaltime si greutate
cn = (h - ch); // calcul nivel
if (cn >= 0 && cg > 0) { // se adauga numai cazurile convenabile
r += cg;
gutui[nr].g = cg;
gutui[nr].n = cn / u;
nr++;
}
}
n = nr;
if (n <= 1) {
out << r;
return 0;
}
qsort(gutui, n, S, cmp_g);
for (i = 0; i < n; i++)
gutui[i].idx = i;
qsort(gutui, n, S, cmp_n);
int maxd = -gutui[0].n, // nr maxim de elem eliminat
maxi = 0, // indicele
maxn;
for (i = 1; i < n; i++) {
if (i - gutui[i].n >= maxd && gutui[i].idx >= maxd) {
maxd = i - gutui[i].n;
maxi = i;
}
}
j = n - 1;
while (gutui[j].n >= j && j >= 0) {
if (gutui[j].idx < maxd)
maxd++;
n--;
j--;
}
for (i = maxi + 1; i < n; i++)
if (gutui[i].idx < maxd)
maxd++;
if (j <= 1) {
out << r;
return 0;
}
maxn = gutui[n - 1].n;
for (i = 0; i <= maxi; i++)
if (gutui[i].idx < maxd) { // || (gutui2[i].n == maxn && gutui2[i].n >= i))
r -= gutui[i].g;
}
out << r;
return 0;
}