Cod sursa(job #819941)

Utilizator ChallengeMurtaza Alexandru Challenge Data 19 noiembrie 2012 20:59:30
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <fstream>
#include <deque>

using namespace std;

const char InFile[]="branza.in";
const char OutFile[]="branza.out";
const int MaxN=100111;

ifstream fin(InFile);
ofstream fout(OutFile);

int N,T,S,C,P[MaxN];
long long sol;
deque<int> Deq;

inline void DeqInsert(int ind)
{
	while(!Deq.empty())
	{
		if(P[Deq.back()]+1LL*S*(ind-Deq.back())<P[ind])
		{
			break;
		}
		Deq.pop_back();
	}
	Deq.push_back(ind);
}

inline void DeqDelete(int ind)
{
	while(!Deq.empty())
	{
		if(Deq.front()>=ind)
		{
			break;
		}
		Deq.pop_front();
	}
}

int main()
{
	fin>>N>>S>>T;
	for(register int i=1;i<=N;++i)
	{
		fin>>P[i]>>C;
		DeqInsert(i);
		DeqDelete(i-T);
		sol+=1LL*C*(P[Deq.front()]+1LL*(i-Deq.front())*S);
	}
	fin.close();

	fout<<sol;
	fout.close();
	return 0;
}