Cod sursa(job #443279)

Utilizator doru.nituNitu Doru Constantin doru.nitu Data 16 aprilie 2010 16:52:20
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include<fstream>
#include<list>

using namespace std;

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

int i,j,n,t,s,p[100005],c[100005],dr,st;
long long a,rez;

struct nod
{
	long long x;
	int poz;
}deq[100005];

int main()
{
	f>>n>>s>>t;
	
	for(i=1;i<=n;++i)
		f>>c[i]>>p[i];
	
	st=1;
	dr=0;
	for(i=1;i<=n;++i)
	{
		a=0;
		if(dr<st)
		{
			a=c[i];
			deq[++dr].x=a+(long long)((n-i)*s);
			deq[dr].poz=i;
		}
		else 
		{
			long long aux=c[i]+(long long)((n-i)*s);
			
			while(dr>=st&&deq[dr].x>aux) --dr;
			deq[++dr].x=aux;
			deq[dr].poz=i;
			
			a=deq[st].x-(n-i)*s;
			if(deq[st].poz==i-t) st++;
		}
		rez+=(a*(long long)(p[i]));
	}
	
	g<<rez<<"\n";

	f.close();
	g.close();
	
	return 0;
}