Cod sursa(job #513206)

Utilizator redls_95Nechita Laura redls_95 Data 15 decembrie 2010 12:47:55
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include<fstream>
using namespace std;
ifstream in("branza.in");
ofstream out("branza.out");
const int N=5000005;
int v[N],v2[N],dq[N];
int st,dr,t,n,s,i;
long long int s1;
inline void dreapta(int i)
{
	while(st<=dr &&v[dq[dr]]+s>=v[i])
	{
		--dr;
	}
}
inline void stanga(int i)
{
	if (i-dq[st]>t) ++st;
}
inline void adauga(int i)
{
	dq[++dr]=i;
}
int main()
{
	in>>n>>s>>t;
	//st=1;
	for(i=1;i<=n;i++)
		in>>v[i]>>v2[i];
	for(i=1;i<=t;i++)
	{
		dreapta(i);
		stanga(i);
	}
	for(;i<=n;++i)
	{
		stanga (i);
		dreapta(i);
		adauga(i);
		//stanga (i);
    	s1=s1+v[dq[st]]*v2[dq[st]];
	}
	out<<s1;
	return 0;
}