Pagini recente » Cod sursa (job #527141) | Cod sursa (job #2119930) | Cod sursa (job #2292250) | Cod sursa (job #1476419) | Cod sursa (job #432278)
Cod sursa(job #432278)
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
long long N, X, L, T = 0;
long long REZ = 0;
const int NMAX = 100100;
long long O[NMAX];
long long lana[NMAX];
long long B[NMAX];
long long ln2[NMAX];
long long timp, ln;
void citire()
{
scanf("%lld%lld%lld",&N,&X,&L);
for(int i = 1; i <= N ; i++)
{
scanf("%lld %lld", &timp, &ln);
timp = 1 + (X - timp) / L;
if(timp > T)
T = timp;
O[i] = timp;
lana[i] = ln;
}
}
void merge_sort(long long l, long long r)
{
long long m = (l + r) >> 1, i, j, k;
if (l == r) return;
merge_sort(l, m);
merge_sort(m + 1, r);
for (i=l, j=m+1, k=l; i<=m || j<=r; )
if (j > r || (i <= m && O[i] > O[j]))
B[k] = O[i], ln2[k++] = lana[i++];
else
B[k] = O[j], ln2[k++] = lana[j++];
for (k = l; k <= r; k++) O[k] = B[k], lana[k] = ln2[k];
}
struct cmp
{
bool operator()(const long long &a, const long long &b)const
{
return lana[a] < lana[b];
}
};
priority_queue <long long, vector<long long>, cmp> Q;
void rezolva()
{
long long nr = 1;
for(long long i = T ; i ; --i)
{
long long j = nr;
while(O[j] == O[nr] && j <= N)
{
Q.push(j);
j++;
}
if(!Q.empty())
{
REZ += lana[Q.top()];
Q.pop();
}
nr = j;
}
}
int main()
{
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
citire();
if(N == 1)
{
printf("%d",lana[1]);
return 0;
}
merge_sort(1, N);
rezolva();
printf("%lld",REZ);
return 0;
}