Cod sursa(job #513204)

Utilizator andrei_stoicaStoica Andrei Florian andrei_stoica Data 15 decembrie 2010 12:46:04
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.55 kb
#include<fstream>
using namespace std;
const int N =100001;
int c[N],p[N],dq[N],n,i,t,s,st=1,dr=0;
long long int suma=0;
ifstream in("branza.in");
ofstream out("branza.out");
inline void stanga(int i)
{
	if (i-dq[st]>t)
		++st;
}

inline void dreapta(int i)
{
	while (st<=dr && c[dq[dr]]+(i-dq[dr])*s>=c[i])
		dr--;
}
inline void adauga(int i)
{
	dq[++dr]=i;
}
int main()
{
	in>>n>>s>>t;
	for (i=1;i<=n;i++)
	{
		in>>c[i]>>p[i];
		stanga(i);
		dreapta(i);
		adauga(i);
		suma=suma+(c[dq[st]]+(i-dq[st])*s)*p[i];
	}
	out<<suma;
}