Cod sursa(job #2264837)

Utilizator maria_sinteaMaria Sintea maria_sintea Data 20 octombrie 2018 11:53:00
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <iostream>
#include <cstdio>
#include <deque>
#define N 100001

using namespace std;

long long n, t, s, p[N], c[N], d[N];
deque <long long> q;

void citire()
{
    scanf("%lld %lld %lld\n", &n, &s, &t);
    for(int i=0;i<n;i++)
        scanf("%lld %lld\n", &c[i], &p[i]);
}

void costuri()
{
    for(int i=0;i<n;i++)
    {
        if(!q.empty() && i>t && c[i-t]-s*(i-t)<=q.front())
            q.pop_front();
        while(!q.empty() && q.back()>c[i]-s*i)
            q.pop_back();
        q.push_back(c[i]-s*i);
        d[i]=q.front()+s*i;
    }
}

void rezultat()
{
    long long r=0;
    for(int i=0;i<n;i++)
        r=r+d[i]*p[i];
    printf("%lld", r);
}

int main()
{
    freopen("branza.in", "r", stdin);
    freopen("branza.out", "w", stdout);

    citire();
    costuri();
    rezultat();
    return 0;
}