Cod sursa(job #357550)

Utilizator silvia_the_bestSilvia Pripoae silvia_the_best Data 19 octombrie 2009 19:39:32
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 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;
unsigned long long c;

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 unsigned long long cost(int i,int j)
{
	return v[i].first + s * (j - i);
}

void solve()
{
	int i;

	for (i = 1; i <= n; ++ i)
	{
		if(!q.empty() && q.front() < i - t)
			q.pop_front();

		while(!q.empty() && cost(q.back(),i) >= v[i].first)
			q.pop_back();

		q.push_back(i);

		c += cost(q.front(), i) * v[i].second;
	}
}
void write()
{
	freopen(FOUT,"w",stdout);

	printf("%llu\n", c);
}
int main()
{
	read();

	solve();

	write();
}