Cod sursa(job #1751072)

Utilizator delia_ioanaCeapa Delia Ioana delia_ioana Data 31 august 2016 18:05:32
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <stdio.h>
#include <deque>
#include <climits>
#define maxn 100010

using namespace std;

int nums[maxn], n, s, t, q;
long long sol = 0;
deque<int> D;

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", &nums[i], &q);
	
		while (!D.empty() && (i - D.back() > t || nums[i] <= nums[D.back()] + s * (i - D.back())))
			D.pop_back();	

		D.push_back(i);

		if (i - D.front() > t)
			D.pop_front();

		sol += (nums[D.front()] + (i - D.front()) * s) * q;
	}
	printf("%lli\n", sol);

	return 0;
}