Cod sursa(job #258944)

Utilizator silvia_the_bestSilvia Pripoae silvia_the_best Data 15 februarie 2009 11:51:38
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <cstdio>
#include <algorithm>
#include <deque>
using namespace std;
#define FIN "branza.in"
#define FOUT "branza.out"
#define N 100007
int n,s,t;
long long cost;
pair <int,int> v[N];
deque <int> q;
void read()
{
	int i;
	freopen(FIN,"r",stdin);
	scanf("%d %d %d", &n, &s, &t);
	for (i = 1; i <= n; ++i)
		scanf("%d %d", &v[i].first, &v[i].second);
} 

inline int costul(int i,int j)
{
	return v[i].first + s * (j - i);
}

void solve()
{
	int i;
	//q.push_back(1);
	for (i = 1; i <= n; ++i)
	{
		if(!q.empty() && q.front() <= i-t)
			q.pop_front();
		while(!q.empty() && costul(q.back(),i) >= v[i].first)
			q.pop_back();
		q.push_back(i);
		cost += (long long)costul(q.front(),i) * v[i].second;
		/*
		sp = 0;
		if ( i - q.front().first > t )
			q.pop_front();
		j = 1;
		while (j <= q.size())
			sp += q[j--]s + s * (j - 1);
		while (v[i].second * )
		*/
	}
}
void write()
{
	freopen(FOUT,"w",stdout);
	printf("%lld\n",cost);
}
int main()
{
	read();
	solve();
	write();
	return 0;
}