Cod sursa(job #1290349)

Utilizator FeriCsiki Francisc Alexandru Feri Data 11 decembrie 2014 09:48:57
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <iostream>
#include <fstream>

using namespace std;

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

long long d[100001],st=1,dr,v[100001],c[100001],n,s,t;

void stanga(int i)
{
    if(i-d[st]==t)
        st++;
}
void dreapta(int i)
{
    while(st<=dr && v[i]<v[d[dr]]+s*(i-d[dr]))
        dr--;
    d[++dr]=i;
}

int main()
{
    int i;
    long long sum=0;
    in>>n>>s>>t;
    for(i=1;i<=n;i++)
    {
        in>>v[i]>>c[i];
    }
    t++;
    for(i=1;i<=n;i++)
    {
        stanga(i);
        dreapta(i);

        sum += (v[d[st]] + s* (i - d[st]) ) * c[i];
        //cout<<sum<<" ";
    }
    out<<sum<<'\n';
    return 0;
}