Pagini recente » Cod sursa (job #693269) | Cod sursa (job #2889006) | Cod sursa (job #2782670) | Cod sursa (job #2127967) | Cod sursa (job #432755)
Cod sursa(job #432755)
#include <stdio.h>
#include <algorithm>
#include <queue>
using namespace std;
#define NMax 100005
#define t first
#define g second
int N, H, U, bst, end[NMax];
pair<int, int> v[NMax];
priority_queue<int> heap;
int main()
{
int i, t;
freopen("gutui.in", "r", stdin);
freopen("gutui.out", "w", stdout);
// citim datele
scanf("%d %d %d", &N, &H, &U);
for (i = 1; i <= N; ++i)
scanf("%d %d", &v[i].t, &v[i].g);
// sortam descrescator dupa timpii de terminare, (H-t)/U
// aceasta sortare e echivalenta cu a sorta crescator dupa t
sort(v+1, v+N+1);
for (i = 1, end[N+1] = -1; i <= N; ++i)
end[i] = (H-v[i].t) / U;
for (i = 1; i <= N; )
{
// tratam toate evenimentele care se petrec in acelasi timp
for (t = end[i]; i <= N && end[i] == t; ++i)
heap.push(v[i].g);
// scoatem din heap maximul cat timp mai avem elemente
// sau cat timp nu am ajuns la un nou eveniment
for (t -= end[i]; t && !heap.empty(); --t)
{
bst += heap.top();
heap.pop();
}
}
printf("%d\n", bst);
return 0;
}