Cod sursa(job #719423)

Utilizator RobertBBadea Corneliu Robert RobertB Data 21 martie 2012 19:53:39
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include<iostream>
#include<fstream>
#include<deque>

using namespace std;

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

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

int main() 
{
	int i,j;
	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 += P[i] * (C[Deque.front()] + S * (i - Deque.front()));
		j = 0;
		while(Deque.back() != j) {
			cout<<Deque[j]<<" ";
			j++;
		}
		cout<<endl;
	}
	g<<cost<<'\n';
	return 0;
}