Pagini recente » Cod sursa (job #2118920) | Cod sursa (job #2198772) | Cod sursa (job #3179705) | Cod sursa (job #2024847) | Cod sursa (job #432673)
Cod sursa(job #432673)
#include <stdio.h>
#include <algorithm>
#include <queue>
using namespace std;
#define NMax 100005
#define PII pair<int, int>
#define t first
#define g second
int N, H, U, bst, end[NMax];
PII v[NMax];
priority_queue<int> heap;
bool operator< (const PII& a, const PII& b)
{
return (H-a.t) / U > (H-b.t) / U;
}
int main()
{
int i, j;
freopen("gutui.in", "r", stdin);
freopen("gutui.out", "w", stdout);
scanf("%d %d %d", &N, &H, &U);
for (i = 1; i <= N; ++i)
scanf("%d %d", &v[i].t, &v[i].g);
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; ++i)
{
// adaugam in heap costurile noilor intervale
for (j = i; j <= N && end[i] == end[j]; ++j)
heap.push(v[j].g);
i = j-1;
// scoatem din heap pana la intalnirea unui nou eveniment
for (j = end[j-1] - end[j]; j && !heap.empty(); --j)
{
bst += heap.top();
heap.pop();
}
}
printf("%d\n", bst);
return 0;
}