Pagini recente » Cod sursa (job #1460727) | Cod sursa (job #54728) | Cod sursa (job #1047231) | Cod sursa (job #106713) | Cod sursa (job #2063036)
#include<stdio.h>
#include<algorithm>
#define MAXN 100000
struct Sheep
{
int profit;
int turns_survived;
};
void Add(int x);
void Rmv(int nod);
void sift(int nod);
void percolate(int nod);
void swap_nodes(int nod1,int nod2);
bool cmp(Sheep,Sheep);
FILE*fin,*fout;
Sheep sheeps[MAXN+1];
int heap[MAXN+1];
int M=0;
int main()
{
fin=fopen("lupu.in","r");
fout=fopen("lupu.out","w");
int N,X,L;
fscanf(fin,"%d%d%d",&N,&X,&L);
for(int i=1;i<=N;i++)
{
int initial_d,wool;
fscanf(fin,"%d%d",&initial_d,&wool);
sheeps[i].profit=wool;
sheeps[i].turns_survived=(X-initial_d)/L+1;
if(sheeps[i].turns_survived<0)
{
sheeps[i].turns_survived=0;
}
}
std::sort(&sheeps[1],&sheeps[N+1],cmp);
int curr=N;
int ans=0;
int Tmax=sheeps[N].turns_survived;
for(int i=Tmax;i>=1;i--)
{
while(sheeps[curr].turns_survived==i && curr>=1)
{
Add(sheeps[curr].profit);
curr--;
}
if(M>0)
{
ans+=heap[1];
Rmv(1);
}
}
fprintf(fout,"%d",ans);
fclose(fin);
fclose(fout);
return 0;
}
bool cmp(Sheep a,Sheep b)
{
if(a.turns_survived==b.turns_survived)
{
return a.profit>b.profit;
}
return a.turns_survived<b.turns_survived;
}
void Add(int x)
{
heap[++M]=x;
percolate(M);
}
void Rmv(int nod)
{
swap_nodes(nod,M);
M--;
if(nod>1 && heap[nod]>heap[nod/2])
{
percolate(nod);
}
else
{
sift(nod);
}
}
void sift(int nod)
{
int son;
do
{
son=0;
if(2*nod+1<=M)
{
if(heap[2*nod]>heap[2*nod+1])
{
son=2*nod;
}
else
{
son=2*nod+1;
}
}
else if(2*nod<=M)
{
son=2*nod;
}
if(heap[nod]>heap[son])
{
son=0;
}
if(son)
{
swap_nodes(nod,son);
nod=son;
}
}while(son);
}
void percolate(int nod)
{
while(nod>1 && heap[nod]>heap[nod/2])
{
swap_nodes(nod,nod/2);
nod=nod/2;
}
}
void swap_nodes(int nod1,int nod2)
{
std::swap(heap[nod1],heap[nod2]);
}