Cod sursa(job #2268634)

Utilizator alex2kamebossPuscasu Alexandru alex2kameboss Data 25 octombrie 2018 08:22:39
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <iostream>
#include <deque>
#include <vector>
#include <queue>
#include <cstdio>
#include <climits>

using namespace std;

int z[100005];
long long n,t,s;
long long rez,c,p;

struct Deque
{
    int q[100005];
    int st = 0, dr = 0;
    void pop_back()
    {
        --dr;
    }
    void pop_front()
    {
        ++st;
    }
    void push_back(int x)
    {
        q[dr++]=x;
    }
    bool empty()
    {
        return st==dr;
    }
    int back()
    {
        return q[dr-1];
    }
    int front()
    {
        return q[st];
    }
}q;

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

    cin>>n>>s>>t;

    for(int i=0;i<n;++i)
    {
        cin>>z[i]>>c;

        while(!q.empty() && z[q.back()]+s*(i-q.back())>z[i])
            q.pop_back();

        q.push_back(i);

        if(i-q.front()>=t)
            q.pop_front();

        rez+=(z[q.front()]+s*(i-q.front()))*c;
    }

    cout<<rez;

    return 0;
}