Cod sursa(job #382185)

Utilizator vlad.doruIon Vlad-Doru vlad.doru Data 13 ianuarie 2010 09:12:48
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <fstream>

using namespace std;

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

int c[1<<17],p[1<<17],dq[1<<17];
int n,s,t,i,st=1,dr=0;

inline void stanga(int i){
    if(i-t>0 && dq[st]==i-t){
        st++;
    }
}
 
void dreapta(int i){
    while ( st<=dr &&  c[i]<=c[dq[dr]]+s*(i-dq[dr])){
        dr--;
    }
    dq[++dr]=i;
}

int main(){
	in>>n>>s>>t;
	++t;
	long long sum=0;
	for(i=1;i<=n;i++){
		in>>c[i]>>p[i];
	}
	for(i=1;i<=n;i++){
        stanga(i);
        dreapta(i);
            sum=sum+(long long)p[i]*(c[dq[st]]+(long long)s*(i-dq[st]));
    }
	out<<sum;
	in.close();
	out.close();
	return 0;
}