Cod sursa(job #462019)

Utilizator toniobFMI - Barbalau Antonio toniob Data 9 iunie 2010 15:45:15
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <fstream>
using namespace std;

ifstream in ("branza.in");
ofstream out ("branza.out");

int n, s, t, deq[100001], c[100001], kg[100001], st = 1, dr;
long long rez;

inline void citire () {
	in >> n >> s >> t;
	++t;
	for (int i = 1; i <= n; ++i) {
		in >> c[i] >> kg[i];
	}
}

void stanga (int i) {
	if (deq[st] == i - t) {
		++st;
	}
}

void dreapta (int i) {
	for (; st <= dr && c[i] <= c[deq[dr]] + (long long)s * (i - deq[dr]); --dr) { }
	deq[++dr] = i;
	
	rez += (c[deq[st]] + (long long) s * (i - deq[st])) * kg[i];
}

int main () {
	citire ();
	
	for (int i = 1; i <= n; stanga (i), dreapta (i), ++i) { }
	
	out << rez;
	
	return 0;
}