Pagini recente » Cod sursa (job #1018369) | Cod sursa (job #2784439) | Cod sursa (job #714316) | Cod sursa (job #85373) | Cod sursa (job #439501)
Cod sursa(job #439501)
#include <fstream>
#include <iostream>
#include <stdlib.h>
using namespace std;
typedef struct nod
{
unsigned int gr,nr;
nod *next;
}nod;
ifstream f("gutui.in");
ofstream g("gutui.out");
unsigned int n,h,u,l,gr,m,nr;
int *heap;
int min(int a, int b)
{
return (a<b) ? a : b;
}
int compare (const void * a, const void * b)
{
return ( ((nod*)a)->nr - ((nod*)b)->nr );
}
void heapify(int k)
{
int s,d;
s=2*k;
d=s+1;
if(s<=m)
{
int temp;
if(heap[k]>heap[s])
if(heap[s]>heap[d] && d<=m)
{
temp=heap[d];
heap[d]=heap[k];
heap[k]=temp;
heapify(d);
}
else
{
temp=heap[s];
heap[s]=heap[k];
heap[k]=temp;
heapify(s);
}
else if(heap[k]>heap[d] && d<=m)
{
temp=heap[d];
heap[d]=heap[k];
heap[k]=temp;
heapify(d);
}
}
}
void printv(nod v[])
{
int i;
for(i=0;i<n;i++)
cout<<v[i].gr<<" ";
cout<<endl;
system("pause");
}
int main()
{
f>>n;
f>>h>>u;
heap=new int[n+1];
int i,j;
nod v[n+1];
for(i=0;i<n;i++)
{
f>>l>>gr;
v[i].gr=gr;
v[i].nr=(h-l)/u+1;
}
qsort(v,n,sizeof(nod),compare);
unsigned int ut=0;
for(i=0;i<n;i++)
{
if(v[i].nr>ut)
{
heap[++m]=v[i].gr;
ut++;
for(j=m/2;j>0;j--)
heapify(j);
}
else if(heap[1]<v[i].gr)
{
heap[1]=v[i].gr;
heapify(1);
}
}
unsigned int max=0;
for(i=1;i<=m;i++)
max+=heap[i];
g<<max<<endl;
f.close();
g.close();
return 0;
}