Cod sursa(job #3174881)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 25 noiembrie 2023 10:40:56
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.6 kb
//Ilie Dumitru
#include<fstream>
#include<deque>
const int NMAX=100005;

int N, S, T;
int p[NMAX], c[NMAX];
int v[NMAX];

int main()
{
	int i, j;
	std::deque<int> dq;
	long long suma=0;
	std::ifstream f("branza.in");
	std::ofstream g("branza.out");

	f>>N>>S>>T;
	for(i=0;i<N;++i)
	{
		f>>c[i]>>p[i];
		v[i]=c[i]-i*S;
	}

	for(i=0;i<N;++i)
	{
		if(!dq.empty() && dq.front()==i-T)
			dq.pop_front();

		while(!dq.empty() && v[dq.back()]>=v[i])
			dq.pop_back();

		dq.push_back(i);

		j=dq.front();

		suma+=p[i]*(long long)((i-j)*S+c[j]);
	}

	g<<suma<<'\n';

	return 0;
}