Cod sursa(job #77129)

Utilizator marius135Dumitran Adrian Marius marius135 Data 13 august 2007 12:55:15
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include<stdio.h>
#define maxn 128*1024

long long v[maxn],poz[maxn],cine[maxn];
long long n,t,s,nr;

void schimba(long a,long b)
{
	v[a] = v[b] ^ v[a] ^(v[b] = v[a]);
	poz[cine[a]] = b;
	poz[cine[b]] = a;
	cine[a] = cine[b] ^ cine[a] ^(cine[b] = cine[a]);
}
long urca(long a)
{
	
	while(a>1 && v[a] < v[a/2])
	{
		schimba(a,a/2);
	}
	return a;
}

void add(long long a,long b)
{
	v[++nr] = a;
	cine[nr] = b;
	poz[b] = nr;
	urca(nr);
	
}
void coboara(long a)
{
	if(a*2>nr) return;
	long fav = a*2;
	if(a*2+1 <= nr && v[fav] > v[fav+1])
		fav = fav+1;
	if(v[fav]<v[a])
	{
		schimba(fav,a);
		coboara(fav);
	}
}
void scoate(long a)
{
	schimba(a,nr);
	nr--;
	urca(a);
	coboara(a);
}
int main()
{
	long long sol =0,p;
	long  i,a,b;
	freopen("branza.in","r",stdin);
	freopen("branza.out","w",stdout);
	
	scanf("%lld %lld %lld",&n,&s,&t);
	for(i=1;i<=n;i++)
	{
		scanf("%ld %ld",&a,&b);
		if(i>t+1) 
			scoate(poz[i-t-1]);
		add(a+(n-i)*s,i);
		p = v[1];
		sol += (long long)b *(p-(n-i)*s);

	}
		
	printf("%lld",sol);
	
	return 0;
}