Pagini recente » Cod sursa (job #2497768) | Cod sursa (job #395965) | Cod sursa (job #2076450) | Istoria paginii runda/abc-ulc/clasament | Cod sursa (job #435945)
Cod sursa(job #435945)
#include <fstream>
#include <stdlib.h>
#include <iostream>
//#include <conio.h>
using namespace std;
ifstream in ("gutui.in");
ofstream out("gutui.out");
int n, h, u, r = 0, nr = 0, *del = NULL;
struct gutuie {
int g; // greutatea
int n; // nr max de gutui culese anterior pt care gutuia ramane accesibila, numit "nivel"
int b; // nr de gutui de dinainte
int idx; // index
};
gutuie *gutui;
// comparara dupa nivel
int cmp_h(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);
}
// comparara dupa nivel
int cmp_nb(const void* fp1, const void* fp2) {
gutuie* f1 = (gutuie*)fp1;
gutuie* f2 = (gutuie*)fp2;
int r = f1->n - f2->n;
return (r == 0 ? f2->b - f1->b : r);
}
void print() {
for (int i = 0; i < nr; i++) {
printf("%d %d %d\n", gutui[i].g, gutui[i].n, gutui[i].b);
}
printf("\n");
}
int main() {
int crt_nr = 0, crt_n = 0, i = 0, j = 0;
in >> n >> h >> u;
gutui = new gutuie[n];
for (i = 0; i < n; i++) {
in >> j >> gutui[i].g;
gutui[i].n = (h - j) / u;
if (gutui[i].n >= 0 && gutui[i].g > 0) { // se elimina cazurile in care nu se poate ajunge
r += gutui[i].g;
nr++;
}
else {
gutui[i].g = 0;
}
}
qsort(gutui, n, sizeof(gutuie), cmp_h); // sortare dupa nivel
/* se pot face maxim k + 1 culegeri de gutui aflate la nivelul k
* daca exista mai mult de k + 1 gutui aflate la nivelul k, se pastreaza cele mai grele k + 1
*/
i = 0;
while (i < n) {
if (gutui[i].n < 0) {
gutui[i].g = 0;
i++;
}
else {
if (gutui[i].n == crt_n) {
crt_nr++;
if (crt_nr > crt_n + 1) { // incepand cu crt_n + 2, se vor elimina toate gutuile cu nivelul curent
while (gutui[i].n == crt_n && i < n) {
// printf("eliminare %d pt ca gutui[%d].n = %d si crt_n = %d si crt_nr = %d\n", i, i, gutui[i].n, crt_n, crt_nr);
r -= gutui[i].g;
gutui[i].g = 0;
nr--;
i++;
}
}
else {
i++;
}
}
else {
crt_n = gutui[i].n;
crt_nr = 1;
i++;
}
}
}
// for (int i = 0; i < n; i++)
// printf("[%d %d]\n", gutui[i].g, gutui[i].n);
// sortare dupa greutate
qsort(gutui, n, sizeof(gutuie), cmp_g);
i = 0;
while (gutui[i].g == 0)
i++;
gutui += i; // raman doar cazurile valide, adica nr gutui, nr <= n
for (i = 0; i < nr; i++)
gutui[i].idx = i;
// sortare dupa nivel
qsort(gutui, nr, sizeof(gutuie), cmp_h);
for (i = 0; i < nr; i++)
gutui[i].b = i;
qsort(gutui, nr, sizeof(gutuie), cmp_nb);
int dels = 0, crt_idx = 0;
while (gutui[nr - 1].n >= gutui[nr - 1].b)
nr--;
int min_idx = gutui[0].idx;
for (i = 1; i < nr; i++)
if (gutui[i].idx < min_idx)
crt_idx = i;
// printf("nr = %d, crt_idx = %d\n", nr, crt_idx);
//print();
// system("pause");
for (i = nr - 1; i >= 0; i--) {
while (gutui[i].g != 0 && gutui[i].n < gutui[i].b - dels) {
r -= gutui[crt_idx].g;
gutui[crt_idx].g = 0;
dels++;
for (j = i; j >= 0; j--)
if (gutui[j].idx == gutui[crt_idx].idx + 1)
crt_idx = j;
}
}
out << r;
return 0;
}