Cod sursa(job #382188)

Utilizator adrian_manducadrian manduc adrian_manduc Data 13 ianuarie 2010 09:15:51
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.57 kb
#include<iostream>
#include<fstream>
using namespace std;
ifstream f("branza.in");
ofstream g("branza.out");

long long c[1<<17],p[1<<17],dr=0,st=1,dq[1<<17],t,s,n;
inline void stanga(int i)
{
	if (i>t && dq[st]==i-t)
		++st;
}
void dreapta(int i)
{
	while(st<=dr&&c[dq[dr]]+(i-dq[dr])*s>=c[i])
		--dr;
	dq[++dr]=i;
}
int main()
{
	f>>n>>s>>t;
	++t;
	long long i,nrf=0;
	for(i=1;i<=n; ++i)
		f>>c[i]>>p[i];
	for(i=1; i<=n; ++i)
	{
		stanga(i);
		dreapta(i);
		nrf=nrf+(c[dq[st]]+(i-dq[st])*s)*p[i];
	}
	g<<nrf;
	f.close();g.close();
	return 0;
}