Cod sursa(job #2173601)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 15 martie 2018 23:01:32
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <bits/stdc++.h>
#define Nmax 100001
#define ll long long
using namespace std;
ifstream f("branza.in");
ofstream g("branza.out");
ll pd[Nmax];
int cost[Nmax];
int cant[Nmax];
deque <ll> dq;
int main()
{
    int n,S,T,i;
    f>>n>>S>>T;
    for(i=1;i<=n;i++)
        f>>cost[i]>>cant[i];
    for(i=1;i<=n;i++)
    {
        if(i>T+1 and !dq.empty() and dq.front()>=cost[i-T-1]-S*(i-T-1))
            dq.pop_front();
        while(!dq.empty() and dq.back()>=cost[i]-S*i)
            dq.pop_back();
        dq.push_back(cost[i]-S*i);
        pd[i]=dq.front()+S*i;
    }
    ll ans=0;
    for(i=1;i<=n;i++)
        ans+=1LL*cant[i]*pd[i];
    g<<ans;

    return 0;
}