Pagini recente » Cod sursa (job #2834394) | Cod sursa (job #198420) | Cod sursa (job #2464236) | Cod sursa (job #1790539) | Cod sursa (job #425667)
Cod sursa(job #425667)
#include <fstream>
#include <stdlib.h>
#include <iostream>
using namespace std;
ifstream in ("gutui.in");
ofstream out("gutui.out");
int n, h, u, r = 0;
struct gutuie {
int h; // inaltimea la care se afla initial
int g; // greutatea
int nc; // nr max de gutui culese dupa care devine inaccesibila
};
/*
int fcmp(const void* fp1, const void* fp2) {
fruct* f1 = (fruct*)fp1;
fruct* f2 = (fruct*)fp2;
float r1 = f1->g / f1->h,
r2 = f2->g / f2->h;
return r1 - r2 < 0 ? -1 : 1;
}
int fcmp1(const void* fp1, const void* fp2) {
fruct* f1 = (fruct*)fp1;
fruct* f2 = (fruct*)fp2;
return f2->g - f1->g;
}
*/
int fcmp2(const void* fp1, const void* fp2) {
gutuie* f1 = (gutuie*)fp1;
gutuie* f2 = (gutuie*)fp2;
return f2->h - f1->h;
}
int main() {
gutuie *gutui, *sel;
in >> n >> h >> u;
gutui = new gutuie[n];
sel = new gutuie[n];
for (int i = 0; i < n; i++) {
in >> gutui[i].h >> gutui[i].g;
gutui[i].nc = (h - gutui[i].h) / u + 1;
}
qsort(gutui, n, sizeof(gutuie), fcmp2); // sortare dupa inaltimea la care se afla
int crtMax = 0, crtNc = 0, si = 0;
bool foundPrev = false;
for (int i = 0; i < n; i++) {
test:
if (gutui[i].nc == crtNc){
foundPrev = true;
if (gutui[i].g > crtMax) {
crtMax = gutui[i].nc;
sel[si] = gutui[i];
}
}
else {
crtMax = 0;
if (foundPrev)
si++;
crtNc++;
foundPrev = false;
goto test;
}
}
for (int i = 0; i < si; i++)
r += sel[i].g;
out << r;
return 0;
}