Pagini recente » Cod sursa (job #804324) | Cod sursa (job #2573302) | Cod sursa (job #2550265) | Cod sursa (job #2634124) | Cod sursa (job #2453745)
#include <fstream>
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
const int NMAX=100005;
int n,x,l,a[NMAX],t[NMAX];
int tmax;
int h[NMAX],indN;
void citire()
{
fin>>n>>x>>l; int d;
for (int i=1; i<=n; i++){
fin>>d>>a[i];
t[i]=1+(x-d)/l;
}
}
void stabTMax()
{
for (int i=1; i<=n; i++)
if (t[i]>tmax)
tmax=t[i];
}
void insertHeap(int i)
{
indN++;
int v=a[i],fiu=indN,tata=indN/2;
while (tata && h[tata]<v){
h[fiu]=tata;
fiu=tata;
tata/=2;
}
h[fiu]=v;
}
void combHeap(int i,int n)
{
int v=h[i],tata=i,fiu=2*i;
while (fiu<=n){
if (fiu<n)
if (h[fiu]<h[fiu+1])
fiu++;
if (h[fiu]>v){
h[tata]=h[fiu];
tata=fiu;
fiu*=2;
}else
fiu=n+1;
}
h[tata]=v;
}
int extractHeap(int n)
{
int v=h[1];
h[1]=h[n];
n--;
combHeap(1,n);
return v;
}
int rezolvare()
{
int sol=0;
for (int j=tmax; j>=1; j--){
for (int k=1; k<=n; k++){
if (t[k]==j)
insertHeap(k);
}
sol+=extractHeap(indN);
}
return sol;
}
int main()
{
citire();
stabTMax();
fout<<rezolvare();
}