Cod sursa(job #719428)

Utilizator RobertBBadea Corneliu Robert RobertB Data 21 martie 2012 19:55:49
Problema Branza Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.59 kb
#include<iostream>
#include<fstream>
#include<deque>

using namespace std;

int C[100000], P[100000];
int N,S,T;
long long cost;
deque <int> Deque;

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

int main() 
{
	int i;
	f>>N>>S>>T;
	for (i = 1; i <= N; i++) {
		f>>C[i]>>P[i];
		while (!Deque.empty() && C[i] < (i - Deque.back())*S + C[Deque.back()]) {
			Deque.pop_back();
		}
		Deque.push_back(i);
		if (i - Deque.front() > T) {
			Deque.pop_front();
		}
		cost += (long long) P[i] * (C[Deque.front()] + S * (i - Deque.front()));
	}
	g<<cost<<'\n';
	return 0;
}