Cod sursa(job #2452093)

Utilizator urweakurweak urweak Data 29 august 2019 15:50:17
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <fstream>
#include <deque>
#include <vector>

#define nmax 100005
using namespace std;
ifstream in("branza.in");
ofstream out("branza.out");

int N, tax, sapt;
deque <int> dq;
vector <pair<int, int>> v;

int depo(int a, int b){
	int rest = 0;
	for(int i = b; i>a; i--)
		rest+=v[i].second;
	int	suma = v[a].first * v[b].second + tax * rest;
	return suma;
}   

int main(){
	 in >> N >> tax >> sapt;

	 for(int i = 0; i<N; i++){
	 	int pret, cant;
	 	in >> pret >> cant;
	 	v.push_back(make_pair(pret, cant));
	 }

	 int suma = 0;

	 for(int i = 0; i<N; i++){
	 	while(!dq.empty() && v[i].first < v[dq.front()].first) dq.pop_front();
	 	dq.push_front(i);
	 	if(dq.back() < i - sapt) dq.pop_back();
	 	if(depo(dq.back(), i) < v[i].first * v[i].second)
	 		suma+=depo(dq.back(), i);
	 	else
	 		suma+=v[i].first * v[i].second;	
	 }
	out << suma;
	return 0;
}