Cod sursa(job #462488)

Utilizator darrenRares Buhai darren Data 11 iunie 2010 08:45:04
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.53 kb
#include<fstream>
#include<deque>
using namespace std;

deque<int> d;
int n, t, s, a[100001];
long long tot;

int main()
{
	ifstream fin("branza.in");
	ofstream fout("branza.out");
	fin >> n >> s >> t;
	for (int i = 1, cant; i <= n; ++i)
	{
		fin >> a[i] >> cant;
		if (!d.empty() && d.back() == a[i - t] + (n - i + t) * s)
			d.pop_back();
		while (!d.empty() && a[i] + (n - i) * s < d.front())
			d.pop_front();
		d.push_front(a[i] + (n - i) * s);
		tot += cant * (d.back() - (n - i) * s);
	}
	fout << tot;
}