Cod sursa(job #1397872)

Utilizator andreeadeacAndreea Ioana Deac andreeadeac Data 23 martie 2015 20:08:21
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 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=1,dr;
long long sum;

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