Cod sursa(job #1853372)

Utilizator giotoPopescu Ioan gioto Data 21 ianuarie 2017 18:35:06
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <cstdio>
using namespace std;

int n, s, t, c[100001], p[100001], dq[100001];
int main()
{
    freopen("branza.in", "r", stdin);
    freopen("branza.out", "w", stdout);
    scanf("%d%d%d", &n, &s, &t);
    int Front = 1, Back = 0;
    long long Sol = 0;
    for(int i = 1; i <= n ; ++i){
        scanf("%d%d", &c[i], &p[i]);
        while(Back >= Front && (c[dq[Back]] * p[i] + p[i] * s * (i - dq[Back]) > c[i] * p[i] || dq[Back] + t < i))
            --Back;
        dq[++Back] = i;
        Sol = Sol + c[dq[Front]] * p[i] + p[i] * s * (i - dq[Front]);
        if(dq[Front] + t <= i + 1)
            ++Front;
    }
    printf("%lld", Sol);
    return 0;
}