Pagini recente » Cod sursa (job #2460467) | Cod sursa (job #1829338) | Cod sursa (job #2484251) | Cod sursa (job #1209576) | Cod sursa (job #487304)
Cod sursa(job #487304)
#include<stdio.h>
#include<algorithm>
#define NMAX 100001
using namespace std;
int n, l, x, var, size, heap[NMAX], aux;
long long sol;
struct str
{
int d,a;
}vec[NMAX];
int cmp(str a,str b)
{
return (a.d > b.d);
}
int left_son(int x)
{
return x*2;
}
int right_son(int x)
{
return x*2+1;
}
int father(int x)
{
return x/2;
}
void sift(int x)
{
int son;
do
{
son = 0;
if(left_son(x)<=size)
{
son = left_son(x);
if(right_son(x)<=size && heap[right_son(x)] > heap[left_son(x)])
{
son = right_son(x);
}
if(heap[son] < heap[x])
son = 0;
}
if(son)
{
aux = heap[son];
heap[son] = heap[x];
heap[x] = aux;
x = son;
}
}while(son);
}
void percolate(int x)
{
while(father(x) > 0 && heap[father(x)] < heap[x])
{
aux = heap[x];
heap[x] = heap[father(x)];
heap[father(x)] = aux;
x = father(x);
}
}
void insert(int x)
{
heap[++size] = x;
//heap[size].d = pas;
percolate(size);
}
void cut(int x)
{
heap[x] = heap[size];
heap[size--] = 0;
if(father(x)>0 && heap[father(x)] < heap[x])
percolate(x);
else sift(x);
}
int main()
{
FILE*f = fopen("lupu.in","r");
fscanf(f,"%d %d %d",&n,&x,&l);
int i = 1;
for(;i<=n;++i)
{
fscanf(f,"%d %d",&vec[i].d,&vec[i].a);
vec[i].d = (x - vec[i].d)/l+1;
if(vec[i].d == 0)printf("%d ",i);
}
fclose(f);
sort(vec+1, vec+n+1, cmp);
int cont;
for( i = vec[1].d, cont = 1; i>=1 && cont<=n;--i)
{
while(vec[cont].d == i && cont<=n)
{
insert(vec[cont++].a);
}
if(size)
{
sol += heap[1];
cut(1);
}
}
FILE*g = fopen("lupu.out","w");
fprintf(g,"%lld\n",sol);
/*for(i = 1;i<=n;++i)
fprintf(g,"%d ",vec[i].d);
fprintf(g,"\n");
for(i=1;i<=n;++i)
fprintf(g,"%d ",vec[i].a);*/
fclose(g);
return 0;
}