Pagini recente » Cod sursa (job #2067957) | Cod sursa (job #334426)
Cod sursa(job #334426)
#include <stdio.h>
#include <algorithm>
using namespace std;
FILE *f,*s;
int n,k,l,i,j,tmax,h[100005],N;
long long int rez;
struct oaie
{
int x;
int y;
int t;
};
oaie v[100005];
int cmp(oaie a, oaie b)
{
return a.t>b.t;
}
int father(int nod)
{
return nod/2;
}
int left_son(int nod)
{
return nod*2;
}
int right_son(int nod)
{
return nod*2+1;
}
int max(int h[100005])
{
return h[1];
}
void percolate(int N, int K)
{
int key=h[K];
while((K>1)&&(key>h[father(K)]))
{
h[K]=h[father(K)];
K=father(K);
}
h[K]=key;
}
void sift(int N, int K)
{
int son;
do
{
son=0;
if(left_son(K)<=N)
{
son=left_son(K);
if(right_son(K)<=N&&h[right_son(K)]>h[left_son(K)])
{
son=right_son(K);
}
if(h[son]<=h[K])
{
son=0;
}
}
if(son)
{
swap(h[K],h[son]);
K=son;
}
} while (son);
}
void insert(int h[100005], int &N, int key)
{
h[++N]=key;
percolate(N, N);
}
void cut(int h[100005], int &N, int K)
{
h[K]=h[N];
--N;
if ((K>1)&&(h[K]>h[father(K)]))
{
percolate(N, K);
}
else
{
sift(N, K);
}
}
int main()
{
f=fopen("lupu.in","r");
s=fopen("lupu.out","w");
fscanf(f,"%d %d %d\n",&n,&k,&l);
for(i=1;i<=n;i++)
{
fscanf(f,"%d %d\n",&v[i].x,&v[i].y);
v[i].t=(k-v[i].x)/l+1;
if(v[i].t>tmax)
tmax=v[i].t;
}
sort(v+1,v+n+1,cmp);
j=1;
for(i=tmax;i>0;i--)
{
while(v[j].t==i&&j<=n)
{
//insert(h,N,v[j].y);
j++;
}
rez+=max(h);
cut(h,N,1);
}
fprintf(s,"%lld\n",rez);
fclose(s);
return 0;
}