Cod sursa(job #1397868)

Utilizator andreeadeacAndreea Ioana Deac andreeadeac Data 23 martie 2015 20:05:48
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 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];
    for(i=1;i<=n;i++){
        if(i>=t)
            stanga(i);
        dreapta(i);
        sum+= ((long long)(c[d[st]]+(long long)s*(i-d[st])))*p[i];
    }
    out<<sum;
    return 0;
}