Pagini recente » Cod sursa (job #1603117) | Cod sursa (job #3238225) | Cod sursa (job #2372881) | Cod sursa (job #1499346) | Cod sursa (job #821195)
Cod sursa(job #821195)
//#include <iostream>
#include <fstream>
using namespace std;
struct oaie {
int d,p;
} oi[100010];
void qsort (oaie *v, int li, int ls);
void adg(int *v, int &n, int x);
int extr(int *v, int &n);
int main()
{
int n,x,l,a;
long long s(0);
ifstream f("lupu.in");
f >> n >> x >> l;
for (int i = 1;i <= n;++i)
{
f >> a >> oi[i].p;
oi[i].d = (x-a)/l + 1;
}
qsort(oi,1,n);
/*for (int i = 1;i <= n;++i)
cout << oi[i].d << " " << oi[i].p << endl;
cout << endl;*/
int fav[100010], k(0), pas(oi[1].d), i(1);
while (pas)
{
while (oi[i].d == pas && i <= n)
{
adg(fav, k, oi[i].p);
++i;
}
s += extr(fav, k);
--pas;
}
ofstream g("lupu.out");
g << s << endl;
/*for (int i = 1;i <= k;++i)
cout << fav[i] << " ";
cout << endl << s;
cin.get();*/
}
int poz (oaie *v, int li, int ls)
{
int i=li, j=ls, i1=0, j1=-1,iaux;
oaie aux;
while (i<j)
{
if (v[i].d < v[j].d)
{
aux=v[i];
v[i]=v[j];
v[j]=aux;
iaux=i1;
i1=-j1;
j1=-iaux;
}
i=i+i1;
j=j+j1;
}
return i;
}
void qsort (oaie *v, int li, int ls)
{
int k;
if (li<ls)
{
k=poz (v,li, ls);
qsort (v,li, k-1);
qsort (v,k+1, ls);
}
}
void adg(int *v, int &n, int x)
{
if (n == 0)
{
v[1] = x;
++n;
return;
}
++n;
int li(1), ls(n), m((n+1)/2);
while (m != li)
{
if (x > v[m])
li = m;
else ls = m;
m = (li+ls)/2;
}
if (x > v[li])
++li;
for (int i = n;i >= li;--i)
v[i+1] = v[i];
v[li] = x;
}
int extr(int *v, int &n)
{
if (n > 0)
{
--n;
return v[n+1];
}
return 0;
}