Cod sursa(job #822911)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 24 noiembrie 2012 11:02:59
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.51 kb
#include<fstream>
#define dim 100010
using namespace std;

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

int n,s,t,i,deque[dim],P[dim],C[dim];
long long D[dim],sum;
int main(){
	
	f>>n>>s>>t;
	
	for(i=1;i<=n;i++)
		f>>C[i]>>P[i];
	
	int p=1;
	int u=0;
	
	for(i=1;i<=n;i++){
		while(C[i]<(C[deque[u]]+(i-deque[u])*s)&&u>=p)
			u--;
		deque[++u]=i;
		if(deque[p]<(i-t))
			p++;
		D[i]=C[deque[p]]+(i-deque[p])*s;
	}
	
	for(i=1;i<=n;i++)
		sum+=D[i]*P[i];
	
	g<<sum;
	
	return 0;
}