Cod sursa(job #305149)

Utilizator FlorianFlorian Marcu Florian Data 16 aprilie 2009 14:20:51
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include<cstdio>
#include<deque>
using namespace std;
#define MAX_N 100003
#define p (Q.front())
#define u (Q.back())
deque<int> Q ;
int a[MAX_N];
int c[MAX_N];
int P[MAX_N];
int S, T, N;
int main()
{
	freopen("branza.in","r",stdin);
	freopen("branza.out","w",stdout);
	scanf("%d%d%d",&N,&S,&T);
	int i, val;
	for(i=1;i<=N;++i) scanf("%d%d",&c[i], &P[i]);
	a[0] = 0;
	for(i=1;i<=N;++i)
	{
		val = c[i] + S * (N-i);
		while(!Q.empty() && c[u] + S * (N-u) > val) Q.pop_back();
		Q.push_back(i);
		a[i] = a[i-1] + P[i] * (c[p] + S * (N-p) - S * (N-i));
		if(p == i-T) Q.pop_front();
	}
	printf("%d\n",a[N]);
	return 0;
}