Cod sursa(job #2626436)

Utilizator andrei-cosmin.bujorBujor Andrei-Cosmin andrei-cosmin.bujor Data 6 iunie 2020 14:42:02
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.69 kb
#include<stdio.h>
#include<deque>
using namespace std;
long long a[100001] , b[100001] , s=0 , sum=0 , t;
int n;
deque < long long > deq;
int main()
{
    freopen("branza.in" , "r" , stdin);
    freopen("branza.out" , "w" , stdout);
    scanf("%d %lld %lld" , &n , &s , &t);
    sum=0;
    for (int i=1 ; i<=n ; ++i)
    {
        scanf("%lld %lld" , &a[i] , &b[i]);
        while(! deq.empty() && a[i] < a[deq.back()] + s*(i-deq.back()))
            deq.pop_back();
        while(! deq.empty() && i-deq.front() > t)
            deq.pop_front();
        deq.push_back(i);
        sum+=a[deq.front()]*b[i]+b[i]*s*(i-deq.front());
    }
    printf("%lld" , sum);
    return 0;
}