Cod sursa(job #547079)

Utilizator razyelxrazyelx razyelx Data 5 martie 2011 21:14:52
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>
#include <deque>

using namespace std;

const int N = 100005;

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

struct week{
	long long cost, req;
} w[N];

long long n,t,s,best;

deque<long long> deq;

void read(){
	long long i;
	
	fin>>n>>s>>t;
	
	for (i=1; i<=n; i++)
		fin>>w[i].cost>>w[i].req;

}

void solve(){
	long long i;
	best = 0;
	
	for (i=1; i<=n; i++){
	
		while (!deq.empty() && w[deq.back()].cost + s*(n - deq.back()) >= w[i].cost + s*(n-i) ) deq.pop_back();
		deq.push_back(i);
		
		while (!deq.empty() && deq.front() <= i-t ) deq.pop_front();

		
		if (w[i].cost * w[i].req > w[i].req * ( w[deq.front()].cost + s*(i-deq.front()) ))
			
			best += w[i].req * ( w[deq.front()].cost + s*(i-deq.front()) );
		else
			best += w[i].cost * w[i].req;
		
			
			
	}
}

void printRez(){
	fout<<best;
}
int main(){
	
	
	read();
	solve();
	printRez();

	return 0;
}