Cod sursa(job #380636)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 6 ianuarie 2010 23:31:40
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <stdio.h>
#define NMAX 100001
#define ll long long
int n,s,t,A[NMAX],B[NMAX],C[NMAX],deq[NMAX],inc,sf;
ll rez;
void read()
{
	scanf("%d%d%d",&n,&s,&t);
	int i;
	for (i=1; i<=n; i++)
		scanf("%d%d",&A[i],&B[i]);
}
inline int min(int x,int y)
{
	return x<y ? x : y;
}
void capat(int i)
{
	if (i-deq[inc]>t)
		inc++;
}
void actualizare(int i)
{
	while (inc!=sf && A[i]<=A[deq[sf-1]]+s*(i-deq[sf-1]))
		--sf;
	deq[sf++]=i;
}
void solve()
{
	int i;
	for (i=1; i<=n; i++)
	{
		actualizare(i);
		capat(i);
		C[i]=A[deq[inc]]+(i-deq[inc])*s;
		rez+=(ll)C[i]*B[i];
	}
}
int main()
{
	freopen("branza.in","r",stdin);
	freopen("branza.out","w",stdout);
	read();
	solve();
	printf("%lld\n",rez);
	return 0;
}