Cod sursa(job #462491)

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

typedef unsigned long long int64;

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

int main()
{
	ifstream fin("branza.in");
	ofstream fout("branza.out");
	fin >> n >> s >> t;
	
	for (int64 i = 1, cant; i <= n; ++i)
	{
		fin >> a[i] >> cant;
		if (!d.empty() && d.back() == a[i - t - 1] + (n - (i - t - 1)) * 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;
}