Pagini recente » Cod sursa (job #1761550) | Cod sursa (job #172417) | Cod sursa (job #143145) | Cod sursa (job #1700056) | Cod sursa (job #439545)
Cod sursa(job #439545)
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
using namespace std;
typedef struct
{
int h, g;
} gutuie;
bool cmp(const gutuie &a, const gutuie &b)
{
return (a.h < b.h);
}
int main()
{
int n, h, u, i, j;
FILE *fin, *fout;
fin = fopen("lupu.in", "rt");
fout = fopen("lupu.out", "wt");
fscanf(fin, "%i %i %i", &n, &h, &u);
vector<gutuie> v(n);
vector<gutuie>::iterator itV;
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;
}
std::sort(v.begin(), v.end(), cmp);
//qsort(v, n, sizeof(gutuie), cmp);
long long 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, "%lli", s);
fclose(fin);
fclose(fout);
return 0;
}