Pagini recente » Cod sursa (job #409880) | Cod sursa (job #615072) | Cod sursa (job #2754747) | Cod sursa (job #2752976) | Cod sursa (job #2072528)
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
int N,X,L,S;
int heap[100009];
struct oaie
{
int dist,lana;
} v[100009];
void urcare(int heap[], int p)
{
while(p>=2 && heap[p]>heap[p/2])
{
swap(heap[p],heap[p/2]);
p=p/2;
}
}
void coborare(int heap[] , int nh , int p)
{
while(2*p<=nh)
{
int r=2*p;
if(r+1<=nh && heap[r]<heap[r+1])
{
r++;
}
if(heap[p]<heap[r])
{
swap(heap[p],heap[r]);
p=r;
}
else
{
break;
}
}
}
bool fct(oaie a,oaie b)
{
return (a.dist < b.dist);
}
void tipar()
{
for(int i=1;i<=N;i++)
{
fout<<v[i].dist<<" "<<v[i].lana<<endl;;
}
}
int main()
{
fin>>N>>X>>L;
for(int i=1;i<=N;i++)
{
fin>>v[i].dist>>v[i].lana;
}
int nrel=0;
int k=1;
for ( int i=1;i<=N;i++)
{
int nivel=X/L-(X-v[i].dist)/L;
v[i].dist=nivel;
}
sort(v+1,v+N+1,fct);
for( int i=0;i<=X/L;i++)
{
for(int j=k; v[j].dist<=i;j++)
{
nrel++;
heap[nrel]=v[j].lana;
urcare(heap ,nrel);
k=j;
}
S=S+heap[1];
swap(heap[1],heap[nrel]);
nrel--;
coborare(heap, nrel , 1);
}
/// tipar();
fout<<S;
fin.close();
fout.close();
return 0;
}