Cod sursa(job #154666)

Utilizator the1dragonIonita Alexandru the1dragon Data 11 martie 2008 13:01:55
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include<stdio.h>
#define N_MAX 128000


long long c[N_MAX], p[N_MAX], sol;
int deq[N_MAX*2];

int main()
{
	freopen("branza.in", "r", stdin);
	freopen("branza.out", "w", stdout);
	
	int n, s, t, i, j, start=1, stop=0;
	scanf("%d %d %d", &n, &s, &t);
	for (i=1; i<=n; i++)
		scanf("%lld %lld", &p[i], &c[i]);
	for (i=1; i<=n; i++)
	{
		for (j=stop; j>=start; j--)
			if  (p[ deq[j] ]+s*(i-deq[j])>p[i]) stop--;
		++stop;
		deq[stop]=i;
		
		for(j=start; j<=stop; j++)
			if (i-deq[j]>t) start++;
			
		sol+=c[i]*(p[deq[start]]+s*(i-deq[start])); 
	}
	printf("%lld\n", sol);
	fclose(stdout);
	return 0;
}