Cod sursa(job #2071494)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 20 noiembrie 2017 18:38:18
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <cstdio>

using namespace std;

FILE *in,*out;

const int nmax = 100005;

int d[nmax],c[nmax],p[nmax];

int main()
{
    in = fopen("branza.in","r");
    out = fopen("branza.out","w");
    int n,s,t,st = 1,dr = 0;
    long long sol = 0;
    fscanf(in,"%d %d %d",&n,&s,&t);
    for(int i = 1;i <= n;i ++)
    {
        fscanf(in,"%d %d",&c[i],&p[i]);
        if(st <= dr && d[st] == i-t)
            st ++;
        while(st <= dr && (c[i] <= (c[d[dr]] + s*(i-d[dr]))))
            dr --;
        d[++dr] = i;
        sol += 1LL*(1LL*p[i] * (1LL*c[d[st]] + 1LL*s * (i- d[st])));
    }
    fprintf(out,"%lld",sol);
    return 0;
}