Cod sursa(job #1397757)

Utilizator andreeadeacAndreea Ioana Deac andreeadeac Data 23 martie 2015 18:58:05
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <fstream>
using namespace std;

ifstream in("branza.in");
ofstream out("branza.out");
int n,s,t;
int c[100001],p[100001],d[100001],st,dr=-1;
long long sum;

void stanga(int i){
    if(i-d[st]==t+1)
        st++;
}

void dreapta(int i){
    //out<<st<<" "<<dr<<d[dr]<<"      ";
    if( st<=dr && c[i] <= c[d[dr]] + (i-d[dr])*s )
        dr--;
    d[++dr]=i;
}

int main()
{
    in>>n>>s>>t;
    int i,j;
    for(i=1;i<=n;i++){
        in>>c[i]>>p[i];
        if(i>t)
            stanga(i);
        dreapta(i);
        //for(j=st;j<=dr;j++)
        //    out<<d[j]<<" ";
        //out<<c[d[st]]<<"\n";
        sum+= (c[d[st]]+(long long)s*(i-d[st]))*p[i];
    }
    out<<sum;
    return 0;
}