Cod sursa(job #755189)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 4 iunie 2012 22:02:34
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include<fstream>
#include<deque>
#include<algorithm>
#define dim 100007
using namespace std;


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

int  s,i,n,c[dim],p[dim],b[dim],v[dim],minu[dim],in,sf,t,cm;
long long  cost;
long long  min(long long  a,long long  b){
	if(a<b)
		return a;
	return b;
}
int main (){
	
	f>>n>>s>>t;
	
	cost=0;
	 for (i=1;i<=n;++i){
        f>>c[i]>>p[i];
        b[i]=c[i]+s*(n-i);
    }
    in=1;
	sf=0;
    for (i=1;i<=n;i++){
		
        while(in<=sf && b[i]<b[v[sf]])
            sf--;
        v[++sf]=i;
        while(v[in]<i-t)
            in++;
        minu[i]=v[in];
    }
    for(i=1;i<=n;i++)
        cost=cost+(long long )p[i]*(c[minu[i]]+(i-minu[i])*s);
	g<<cost<<"\n";
	return 0;
}