Cod sursa(job #299967)

Utilizator SheepBOYFelix Liviu SheepBOY Data 7 aprilie 2009 10:15:41
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include<stdio.h>
struct Dq{
	long long p,c;
	int cp;
};
Dq deque[100000];
Dq aux;
int st,end;
int n,t,s,ft,cop;
long long sum;
void add(Dq a);
int main()
{
	freopen("branza.in","r",stdin);
	freopen("branza.out","w",stdout);
	scanf("%d%d%d",&n,&s,&t);
	st=1;
	for(int i=1;i<=n;++i)
	{
		
		scanf("%d%d",&aux.c,&aux.p);
		
		if(i - deque[st].p > t)
			++st;
		
		cop=aux.p;
		aux.p=i;
		
		add(aux);
		
		sum += (deque[st].c + (i-deque[st].p)*s) * cop;
		
	}
	printf("%lld",sum);
	return 0;
}

void add(Dq a)
{
	/*
	i=st;
	if(ft)
	{
		while(a.c>deque[i].c+s&&deque[i].c)
		{
			deque[i].p++;
			deque[i].c+=s;
			deque[i].cp=cop;
			++i;
		}
	}
	ft=1;
	deque[i].p=aux.p;
	deque[i].c=aux.c;
	deque[i].cp=cop;
	end=i;
	*/
	while(end && deque[end].c + s*(a.p - deque[end].p) >= a.c)
		--end;
	deque[++end] = a;
}