Cod sursa(job #2514995)

Utilizator 1chiriacOctavian Neculau 1chiriac Data 27 decembrie 2019 15:42:29
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <bits/stdc++.h>

using namespace std;
int n,s,t,cost[100005],suma;pair <int,int> zile[100005];
deque <int> chestie;
int main () {
	freopen("branza.in","r",stdin);
	freopen("branza.out","w",stdout);
	scanf("%d%d%d", &n, &s, &t);
	for(int i=1;i<=n;++i)
		scanf("%d%d", &zile[i].first, &zile[i].second);
	cost[1]=zile[1].first*zile[1].second;chestie.push_front(1);
	for(int i=2;i<=n;++i) {
		while(!chestie.empty() && i-chestie.front()>t)
			chestie.pop_front();
		while(!chestie.empty() && (i-chestie.front())*s*zile[i].second+zile[i].second*zile[chestie.front()].first>zile[i].first*zile[i].second)
			chestie.pop_front();
		if(chestie.empty())
			cost[i]=zile[i].second*zile[i].first,chestie.push_back(i);
		else
			cost[i]=(i-chestie.front())*s*zile[i].second+zile[i].second*zile[chestie.front()].first;
	}
	for(int i=1;i<=n;++i)
		suma+=cost[i];
	printf("%d", suma);
	return 0;
}