Pagini recente » Cod sursa (job #1346874) | Cod sursa (job #2356087) | Cod sursa (job #2783017) | Borderou de evaluare (job #2051294) | Cod sursa (job #352709)
Cod sursa(job #352709)
#include <fstream.h>
struct oaie{ int t,a; } v[100001],c[100001];
int N,X,L,H[100001],NH=0;
void mergesort(int,int);
void merge(int,int,int);
int search(int);
void up(int);
void down(int);
int main()
{
int i,j,S=0,maxT=0,first,last;
ifstream in("lupu.in");
in>>N>>X>>L;
for(i=1;i<=N;i++)
{
in>>v[i].t>>v[i].a;
if(X-v[i].t>=0)
{
v[i].t=(X-v[i].t)/L+1;
if(v[i].t>maxT) maxT=v[i].t;
}
else{ i--; N--; }
}
in.close();
mergesort(1,N);
for(i=maxT;i>=1;i--)
{
first=last=search(i);
first--; last++;
while(first>=1 && v[first].t==i) first--;
while(last<=N && v[last].t==i) last++;
first++; last--;
for(j=first;j<=last;j++)
{
H[++NH]=v[j].a;
up(NH);
}
S+=H[1];
H[1]=H[NH--]; down(1);
}
ofstream out("lupu.out"); out<<S<<'\n'; out.close();
return 0;
}
void mergesort(int first,int last)
{
int mid;
if(first<last)
{
mid=(first+last)/2;
mergesort(first,mid);
mergesort(mid+1,last);
merge(first,mid,last);
}
}
void merge(int first,int mid,int last)
{
int i=first,j=mid+1,k=first;
while(i<=mid && j<=last)
{
if(v[i].t<v[j].t) c[k]=v[i++];
else c[k]=v[j++];
k++;
}
while(i<=mid) c[k++]=v[i++];
while(j<=last) c[k++]=v[j++];
for(i=first;i<k;i++) v[i]=c[i];
}
int search(int key)
{
int first=1,mid,last=N;
while(first<=last)
{
mid=(first+last)/2;
if(v[mid].t<key) first=mid+1;
if(v[mid].t>key) last=mid-1;
if(v[mid].t==key) return mid;
}
return 0;
}
void up(int K)
{
int key=H[K];
while(K>1 && key>H[K/2])
{
H[K]=H[K/2];
K/=2;
}
H[K]=key;
}
void down(int K)
{
int son,left,right,swap;
do
{
son=0; left=K*2;
if(left<=NH)
{
son=left; right=K*2+1;
if(right<=NH && H[son]<H[right])
son=right;
if(H[son]<=H[K]) son=0;
}
if(son){ swap=H[son]; H[son]=H[K]; H[K]=swap; K=son; }
}while(son);
}