Cod sursa(job #2362253)

Utilizator AlexPascu007Pascu Ionut Alexandru AlexPascu007 Data 3 martie 2019 01:31:18
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.53 kb
#include <fstream>
#include <deque>
#define DIM 100010
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
int n,s,t,i,sol,c[DIM],p[DIM];
deque<int> q; //in deque vom tine ultimele t pozitii cu cost minim
int main() {
	fin>>n>>s>>t;
	for (i=1;i<=n;i++)
		fin>>c[i]>>p[i];
	for (i=1;i<=n;i++) {
		while (!q.empty()&&c[i]<=c[q.back()]+s*(i-q.back()))
			q.pop_back();
		q.push_back(i);
		if (i-q.front()>t)
			q.pop_front();
		sol+=p[i]*(c[q.front()]+s*(i-q.front()));
	}
	fout<<sol;
	return 0;
}