Pagini recente » Cod sursa (job #776712) | Cod sursa (job #1575808) | Cod sursa (job #2928620) | Cod sursa (job #3166795) | Cod sursa (job #1320129)
#include <fstream>
#include <algorithm>
#include <queue>
using namespace std;
ifstream f("lupu.in");
ofstream g("lupu.out");
int n, x, L, T = 0;
long long S = 0;
const int Max = 100100;
int O[Max];
int lana[Max];
int B[Max];
int ln2[Max];
int timp, ln;
priority_queue <int, vector<int> > Q;
void citire()
{
f>>n>>x>>L;
for(int i = 1; i <= n ; i++)
{
f>>timp>>lana[i];
timp = 1 + (x - timp) / L;
if(timp > T)
T = timp;
O[i] = timp;
}
}
void merge_sort(int l, int r)
{
int 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];
}
}
void rezolva()
{
int nr = 1, j = 0;
for(int i = T ; i ; --i)
{
if(i == O[nr])
{
j = nr;
while(O[j] == O[nr] && j <= n)
{
Q.push(lana[j]);
j++;
}
}
if(!Q.empty() )
{
S += Q.top();
Q.pop();
}
nr = j;
}
}
int main()
{
citire();
if(n == 1)
{
g<<lana[1];
return 0;
}
merge_sort(1, n);
rezolva();
g<<S;
return 0;
}