Cod sursa(job #509530)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 11 decembrie 2010 11:45:01
Problema Branza Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include<iostream>
#include<fstream>
using namespace std;
ifstream aa("branza.in");
ofstream ss("branza.out");
int n,s,t,v[10001],x[12001],st=1,dr=0,d[10001],i,k;
long long sum;
inline void stanga(int i)
{
	if (d[st]==i-t) {
		++st;
	}
}
inline void dreapta(int i){
	while(st<=dr && v[i]<=v[d[dr]] + (long long)s * (i-d[dr]))         
		--dr; 
} 
inline void adauga(int i) {
	d[++dr]=i;
}

int main() {
	aa >> n >> s >> t;
	for (i=1;i<=n;++i) {
		aa >> v[i] >> x[i];
	}
	++t;
	for(i=1;i<=n;++i) { 
		stanga(i); 
		dreapta(i); 
		adauga(i); 
		sum+=(v[d[st]]+(long long)s * (i - d[st]))*x[i]; 
	}
	ss << sum;	
	return 0;
}