Cod sursa(job #2057706)

Utilizator alexge50alexX AleX alexge50 Data 4 noiembrie 2017 16:58:10
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <stdio.h>

#define MAX_N 100000

namespace My
{
  template< class T >
  class deque
  {
  public:

    deque() {m_left = 0, m_right = -1;}

    T peak_front(){ return m_deque[m_left]; }
    T peak_back(){ return m_deque[m_right]; }

    void pop_front() {m_left++;}
    void push_back(T val) {m_deque[++m_right] = val;}
    void pop_back() {m_right--;}

    bool is_empty() {return m_left > m_right;}
  private:
    T m_deque[MAX_N];
    int m_left, m_right;
  };
};

struct elem
{
    int pos, val;


    elem() {}

    elem(int _pos, int _val): pos(_pos), val(_val) {}
};

My::deque<elem> deque;

int main()
{
    FILE *fin = fopen("branza.in", "r"),
         *fout = fopen("branza.out", "w");
    int n, s, t;
    long long sum;

    fscanf(fin, "%d %d %d", &n, &s, &t);

    sum = 0;
    for(int i = 0; i < n; i++)
    {
        int c, q;
        fscanf(fin, "%d %d", &c, &q);

        if(!deque.is_empty() && deque.peak_front().pos == i - t)
            deque.pop_front();

        while ( !deque.is_empty() &&
                    c <= deque.peak_back().val + s * (i - deque.peak_back().pos)
               )
                deque.pop_back();

        deque.push_back(elem(i, c));

        sum += ((long long)(deque.peak_front().val + s * (i - deque.peak_front().pos))) * ((long long) q);
    }

    fprintf(fout, "%lld", sum);

    fclose(fin);
    fclose(fout);
    return 0;
}