Cod sursa(job #1184643)

Utilizator IliescuDanAndreiIliescu Dan Andrei IliescuDanAndrei Data 13 mai 2014 18:41:27
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <fstream>
using namespace std;
ifstream in("branza.in");
ofstream out("branza.out");
int n, s, t, st = 1, dr, c[100001], p[100001], d[100001];
long long suma;

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

void dreapta(int x)
{
    while(st <= dr && c[x]<c[d[dr]]+s*(x-d[dr]))
        dr--;
    d[++dr]=x;

}

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