Cod sursa(job #2334989)

Utilizator shantih1Alex S Hill shantih1 Data 3 februarie 2019 14:13:23
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.51 kb
#include <iostream>
#include <fstream>
#include <deque>
#define ll long long

using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");

ll n,s,t,i,j,nr,v,ct;
ll rez;
struct per
{	ll v,p; };
deque<per> dq;

int main() {
	
	fin>>n>>s>>t;
	for(i=1;i<=n;i++)
	{
		fin>>v>>ct;
		while(!dq.empty() && dq.back().v+s*(i-dq.back().p) > v)
			dq.pop_back();
		while(!dq.empty() && dq.front().p <= i-t)
			dq.pop_front();
		
		dq.push_back({v,i});
		rez+=(dq.front().v+s*(i-dq.front().p))*ct;
	}
	fout<<rez<<"\n";
}