Cod sursa(job #462003)

Utilizator mihai995mihai995 mihai995 Data 9 iunie 2010 15:29:52
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.48 kb
#include <fstream>
using namespace std;

int v[1<<17],dq[1<<17],n,k,t,st=1,dr;

ifstream in("branza.in");
ofstream out("branza.out");

inline void s(int x)
{
	if (st<=dr && v[st]==x-k)
		st++;
}

void d(int x)
{
	while (st<=dr && v[dq[dr]]+t*(x-dq[dr])>=v[x])
		dr--;
	dq[++dr]=x;
}

int main()
{
	int i,x,y,nr=0;
	in>>n>>t>>k;
	for (i=1;i<=n;i++)
	{
		in>>x>>y;
		v[i]=x;
		s(i);
		d(i);
		nr+=(v[dq[st]]+t*(i-dq[st]))*y;
	}
	out<<nr<<"\n";
	return 0;
}