Cod sursa(job #2730767)

Utilizator icnsrNicula Ionut icnsr Data 26 martie 2021 20:25:08
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.78 kb
#include <cstddef>
#include <vector>
#include <fstream>

template<typename T>
class Deque
{
public:
    Deque() = default;
    Deque(const std::size_t count, const T& value)
        : capacity(count)
    {
        data = new T[count];
        for(std::size_t i = 0; i < count; ++i)
        {
            data[i] = value;
        }
        endidx = count;
    }
    ~Deque()
    {
        if(data != nullptr)
        {
            delete[] data;
        }
    }

    void push_back(const T& value)
    {
        if(data != nullptr)
        {
            if(endidx == capacity)
            {
                extend_right(capacity * 2);
            }
            data[endidx] = value;
            ++endidx;
        }
        else
        {
            data = new T[1];
            *data = value;
            capacity = 1;
            endidx = 1;
        }
    }

    void push_front(const T& value)
    {
        if(data != nullptr)
        {
            if(begidx == 0)
            {
                extend_left(size(), size() * 2);
            }
            --begidx;
            data[begidx] = value;
        }
        else
        {
            data = new T[1];
            *data = value;
            capacity = 1;
            endidx = 1;
        }
    }

    void pop_back()
    {
        --endidx;
    }

    void pop_front()
    {
        ++begidx;
    }

    T& front()
    {
        return data[begidx];
    }

    T& back()
    {
        return data[endidx - 1];
    }

    const T& front() const
    {
        return data[begidx];
    }

    const T& back() const
    {
        return data[endidx - 1];
    }

    T* begin()
    {
        return (data + begidx);
    }

    T* end()
    {
        return (data + endidx);
    }

    const T* begin() const
    {
        return (data + begidx);
    }

    const T* end() const
    {
        return (data + endidx);
    }

    std::size_t size() const
    {
        if(data != nullptr)
        {
            return endidx - begidx;
        }
        return 0;
    }

    bool empty() const
    {
        return (data == nullptr || begidx == endidx);
    }

private:
    void extend_left(const std::size_t currentsize, const std::size_t newsize)
    {
        T* newdata = new T[newsize];

        const std::size_t difference = newsize - currentsize;
        for(std::size_t i = begidx + difference; i < endidx + difference; ++i)
        {
            newdata[i] = data[i - difference];
        }

        delete[] data;

        data = newdata;
        begidx += difference;
        endidx += difference;
        capacity = newsize;
    }

    void extend_right(const std::size_t newsize)
    {
        T* newdata = new T[newsize];
        for(std::size_t i = begidx; i < endidx; ++i)
        {
            newdata[i] = data[i];
        }

        delete[] data;

        data = newdata;
        capacity = newsize;
    }

private:
    T* data = nullptr;
    std::size_t begidx = 0;
    std::size_t endidx = 0;
    std::size_t capacity = 0;
};

int main()
{
    std::ifstream fin("branza.in");
    std::ofstream fout("branza.out");

    unsigned N;
    unsigned S;
    unsigned T;
    fin >> N >> S >> T;

    std::vector<std::pair<unsigned, unsigned>> vec;
    for(std::size_t i = 0; i < N; ++i)
    {
        unsigned v1;
        unsigned v2;
        fin >> v1 >> v2;
        vec.push_back(std::make_pair(v1, v2));
    }

    Deque<unsigned> deq;
    unsigned suma = 0;
    for(unsigned i = 0; i < N; ++i)
    {
        while(!deq.empty() && vec[i].first <= vec[deq.back()].first + S * (i - deq.back()))
        {
            deq.pop_back();
        }
        deq.push_back(i);

        if(i - deq.front() == T)
        {
            deq.pop_front();
        }

        const unsigned d_idx = deq.front();
        suma += vec[i].second * (vec[d_idx].first + S * (i - d_idx));
    }

    fout << suma << '\n';
}