Cod sursa(job #2454061)

Utilizator urweakurweak urweak Data 7 septembrie 2019 12:19:04
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.53 kb
#include <bits/stdc++.h>
using namespace std;

int N, S, W;
int cost[100000], kg[100000];
long long ans = 0;

deque <int> d;

int main(){
	ifstream in("branza.in");
	ofstream out("branza.out");

	in >> N >> S >> W;

	for(int i = 0; i<N; i++){

		in >> cost[i] >> kg[i];

		while(!d.empty() && cost[d.back()] + 1LL * (i - d.back()) * S > cost[i]) d.pop_back();
		d.push_back(i);

		if(i - d.front() > W) d.pop_front();

		ans+=(cost[d.front()] + 1LL * (i - d.front()) * S) * kg[i]; 
	}
	out << ans;
	return 0;
}