Cod sursa(job #515701)

Utilizator PavelPavel Ana-Oriana Pavel Data 22 decembrie 2010 10:45:16
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include<fstream>

using namespace std;

const int N = 100001;

struct branza
{
	int pret,cant;
};
branza v[N];
int n,st=1,dr=0,t,s;
int d[N];

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

inline void dreapta(int i)
{
	while(st<=dr && v[d[dr]].pret+(long long)(i-d[dr])*s >= v[i].pret)
		--dr;
}

inline void stanga(int i)
{
	if(d[st]==i-t)
		++st;
}
int main()
{
	long long r = 0;
	int i;
	in>>n>>s>>t;
	for(i=1;i<=n;i++)
		in>>v[i].pret>>v[i].cant;
	++t;
	for(i=1 ; i<=n ; ++i)
	{
		stanga(i);
		dreapta(i);
		d[++dr] = i;
		r += (v[d[st]].pret + (long long)(i - d[st]) * s)*v[i].cant;
	}
	out<<r<<"\n";
	return 0;
}