Cod sursa(job #77145)

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

long long v[maxn*2],poz[maxn],cine[maxn];
long long n,t,s,nr=0,x[maxn],y[maxn];

void schimba(long a,long b)
{
	long aux ;
	/*aux = v[a];
	v[a] = v[b];
	v[b] = aux;*/
	v[a] = v[b] ^ v[a]^(v[b] = v[a]);
	poz[cine[a]] = b;
	poz[cine[b]] = a;
	cine[a] = cine[a] ^ cine[b] ^ (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  long i,a,b;
	freopen("branza.in","r",stdin);
	freopen("branza.out","w",stdout);
	
	//scanf("%lld %lld %lld",&n,&s,&t);
	cin>>n>>s>>t;
	for(i=1;i<=n;i++)
	{
		//scanf("%ld %ld",&a,&b);
		cin>>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);

	}
	long j;
	/*for(i=1;i<=n;i++)
	{
		cin>>x[i]>>y[i];
		long long add =0;
		long long min = x[i];
		for(j=i;j>=i-t&& j>0;add+=s,j--)
		{
			if(x[j]+add < min)
				min = x[j]+add;
		}
		sol+=min*y[i];
	}*/
		
//	printf("%lld",sol);
	cout<<sol;
	
	return 0;
}