Cod sursa(job #409627)

Utilizator loginLogin Iustin Anca login Data 3 martie 2010 19:34:47
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
# include <fstream>
# include <iostream>
using namespace std;
struct branza{
	int p, c;};
int n, s, t; 
long long sol;
branza v[100003];

void read ()
{
	ifstream fin ("branza.in");
	fin>>n>>s>>t;
	for (int i=1;i<=n;i++)
		fin>>v[i].c>>v[i].p;
}

void solve ()
{
	branza dq[100003];
	int st, dr;
	st=dr=1;
	dq[st].c=v[1].c;
	dq[st].p=1;
	for (int i=1;i<=n;i++)
	{
		if (v[i].c*v[i].p<=dq[st].c*v[i].p+(i-dq[st].p)*s*v[i].p)
			sol+=v[i].c*v[i].p;
		else
			sol+=dq[st].c*v[i].p+(i-dq[st].p)*s*v[i].p;
		if (i-dq[st].p==t)
			st++;
		while (st<=dr && v[i].c<dq[dr].c+s)--dr;
		dq[++dr].c=v[i].c;
		dq[dr].p=i;
	}
}

int main()
{
	read();
	solve ();
	ofstream fout ("branza.out");
	fout<<sol;
	return 0;
}