Cod sursa(job #299952)

Utilizator mottyMatei-Dan Epure motty Data 7 aprilie 2009 10:02:28
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include<cstdio>
#include<deque>
#include<vector>
#define a first
#define b second
using namespace std;

typedef pair<int,int> bz;

deque <int> q;

vector <bz> v;

int n,t,s;

long long sum;

void cit()
{
	bz y;
	scanf("%d%d%d",&n,&t,&s);
	for( int i=0 ; i<n ; ++i )
	{
		scanf("%d%d",&y.a,&y.b);
		v.push_back(y);
	}
}

void stanga( int i )
{
	if(i - q.front() > s)
		q.pop_front();
}

void dreapta( int i )
{
	while(!q.empty() && (i - q.back()) * t + v[q.back()].a >= v[i].a )
		q.pop_back();
	q.push_back(i);
}

void calc()
{
	for( int i=0 ; i<n ; ++i )
	{
		stanga(i);
		dreapta(i);
		sum +=(long long) (v[q.front()].a + (i - q.front()) * t) * v[i].b;
	}
	printf("%lld\n",sum);
}

int main()
{
	freopen("branza.in","r",stdin);
	freopen("branza.out","w",stdout);
	cit();
	calc();
	return 0;
}