Cod sursa(job #571318)

Utilizator dornescuvladVlad Eugen Dornescu dornescuvlad Data 4 aprilie 2011 12:02:03
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <iostream>
#include <fstream>

using namespace std;

const char iname[] = "branza.in";
const char oname[] = "branza.out";
const int  nmax    = 100005;

ifstream fin(iname);
ofstream fout(oname);

long long dp[nmax], t, s, p, n, pret[nmax], C[nmax], dq[nmax], sol;
long long i, front, back;

int main()
{
	fin >> n >> s >> t;
	for(i = 1; i <= n; i ++)
		fin >> C[i] >> pret[i];
	
	
	front = 1, back = 0;
	for(i = 1; i <= n; i ++)
	{	
		if(i - t > dq[front])
			++front;
		while(C[i] <= C[dq[back]] + (i - dq[back]) * s && back > 0 && front <= back)
			--back;
		dq[++back] = i;
		sol = sol + (C[dq[front]] + (i - dq[front]) * s) * pret[i];
	}
	fout << sol << "\n";
	return 0;
}