Cod sursa(job #514392)

Utilizator ioanabIoana Bica ioanab Data 18 decembrie 2010 16:57:56
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <fstream>
using namespace std;

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

const int N=100005;

int c[N],dq[N],p[N];
int n,s,t,st,dr;
long long sum;

void dreapta(int i)
{
	while(st<=dr && c[dq[dr]]+(long long)s*(i-dq[dr])>=c[i])
		dr--;
}

void stanga(int i)
{
	if(i-dq[st]==t)
		++st;
}
void adauga(int i)
{
	dq[++dr]=i;
}

int main()
{
		int i;
		in>>n>>s>>t;
		st=1;
		dr=0;
		for(i=1;i<=n;i++)
			in>>c[i]>>p[i];
		for(i=1;i<=t;i++)
		{
			dreapta(i);
			dq[++dr]=i;
			sum+=(c[dq[st]]+(i-dq[st])*s)*p[dq[st]];
		}
		for(;i<=n;i++)
		{
			stanga(i);
			dreapta(i);
			adauga(i);
			sum+=(c[dq[st]]+(i-dq[st])*s)*p[i];
		}
		
		out<<sum<<"\n";
		return 0;
}