Cod sursa(job #2268646)

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

using namespace std;

long long n,t,s;
long long rez;

struct branza
{
    long long pret;
    int c, poz;
}b;

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

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

    scanf("%d %d %d\n", &n, &s, &t);

    for(int i=0;i<n;++i)
    {
        scanf("%lld %d\n", &b.pret, &b.c);
        b.poz = i;

        while(!q.empty() && q.back().pret+s*(i-q.back().poz)>b.pret)
            q.pop_back();

        q.push_back(b);

        rez+=(q.front().pret+s*(i-q.front().poz))*b.c;

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

    cout<<rez;

    return 0;
}