Pagini recente » Cod sursa (job #1044430) | Cod sursa (job #37267) | Cod sursa (job #1875762) | Cod sursa (job #2728952) | Cod sursa (job #439025)
Cod sursa(job #439025)
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
using namespace std;
typedef struct
{
int h, g;
} gutuie;
gutuie v[100000];
int cmp(const void *a, const void *b)
{
gutuie x, y;
x = *(gutuie *) a;
y = *(gutuie *) b;
if (x.h == y.h) return y.g - x.g;
return x.h - y.h;
}
int max(int a, int b)
{
if (a > b) return a;
return b;
}
int main()
{
int n, h, u, i, j;
FILE *fin, *fout;
fin = fopen("gutui.in", "rt");
fout = fopen("gutui.out", "wt");
fscanf(fin, "%i %i %i", &n, &h, &u);
for (i = 0; i < n; i++)
{
fscanf(fin, "%i %i", &(v[i].h), &(v[i].g));
v[i].h = (h - v[i].h) / u + 1;
if(v[i].h < 0) v[i].h = 0;
}
qsort(v, n, sizeof(gutuie), cmp);
int s = 0;
vector<int> a;
vector<int>::iterator it;
j = v[n-1].h;
i = n-1;
while (i >= 0 && j > 0)
{
if (j == v[i].h)
{
a.push_back(v[i].g);
push_heap(a.begin(), a.end());
i--;
continue;
}
j--;
if (a.empty()) continue;
pop_heap(a.begin(), a.end());
s += a.back();
a.pop_back();
}
while (j > 0 && !a.empty())
{
pop_heap(a.begin(), a.end());
s += a.back();
a.pop_back();
j--;
}
fprintf(fout, "%i", s);
fclose(fin);
fclose(fout);
return 0;
}