Submission #872578

#	Time	Username	Problem	Language	Result	Execution time	Memory
872578		sleepntsheep	Peru (RMI20_peru)	C++17	0 / 100	0 ms	348 KiB

peru

#include "peru.h"
#include <cassert>
#include <tuple>
#include <utility>
#include <iostream>
#include <algorithm>
#include <stack>

template <typename T, const T& (*F)(const T&, const T&)>
struct stack
{
    std::stack<T> a, b;

    void push(const T &v)
    {
        b.push(a.size() ? F(b.top(), v) : v);
        a.push(v);
    }

    bool empty()
    {
        return a.empty();
    }

    size_t size()
    {
        return a.size();
    }

    T top()
    {
        return a.top();
    }

    T op()
    {
        return b.top();
    }

    void pop()
    {
        a.pop(); b.pop();
    }

    void swap(stack &x) {a.swap(x.a);b.swap(x.b);}
};

template <typename T, const T& (*F)(const T&, const T&)>
struct deque
{
    stack<T, F> f, b, t;

    deque() { }

    void rebalance() {
        bool a = false;
        if (b.empty()) {a = true; f.swap(b);}
        size_t sz = b.size() / 2;
        while (sz--) {t.push(b.top()); b.pop();}
        while (!b.empty()) {f.push(b.top()); b.pop();}
        while (!t.empty()) {b.push(t.top()); t.pop();}
        if (a) f.swap(b);
    }

    void push_back(const T &v)
    {
        b.push(v);
    }

    void pop_front()
    {
        if (f.empty()) rebalance();
        f.pop();
    }

    void pop_back()
    {
        if (b.empty()) rebalance();
        b.pop();
    }

    T front()
    {
        if (f.empty()) rebalance();
        return f.top();
    }

    T back()
    {
        if (b.empty()) rebalance();
        return b.top();
    }

    T op()
    {
        if (f.empty()) return b.op();
        if (b.empty()) return f.op();
        return F(f.op(), b.op());
    }

    size_t size()
    {
        return f.size() + b.size();
    }
};

using i64 = long long;
using u64 = unsigned long long;

int solve(int n, int k, int* v)
{
    i64 *dp = new i64[n];
    for (int i = 0; i < n; ++i) dp[i] = 1e18;

    deque<std::tuple<i64, i64>, std::min> dq;

    for (int i = 0; i < k; ++i)
    {
        while (dq.size() && v[std::get<1>(dq.back())] < v[i]) dq.pop_back();
        dq.push_back({(dq.size() ? dp[std::get<1>(dq.back())] : 0) + v[i], i});
        dp[i] = v[std::get<1>(dq.front())];
    }

    for (int i = k; i < n; ++i)
    {
        while (dq.size() && v[std::get<1>(dq.back())] <= v[i]) dq.pop_back();

        if (dq.size())
        {
            dp[i] = dp[std::get<1>(dq.op())] + v[i];
            dq.push_back({dp[std::get<1>(dq.back())] + v[i], i});
        }
        else
        {
            dq.push_back({dp[i-k] + v[i], i});
        }

        while (dq.size() && std::get<1>(dq.front()) + k + 1 < i) dq.pop_front();

        dp[i] = std::min({dp[i], dp[i-k] + v[std::get<1>(dq.front())], dp[std::get<1>(dq.op())] + v[i]});
    }

    //for (int i = 0; i < n; ++i) std::cout << dp[i] << '\n'; std::cout<<std::endl;

    constexpr const i64 M = 1000000007;
    i64 x = 0, p23 = 1;
    for (u64 i = n; i--; p23 = (p23 * 23) % M) x = (x + dp[i] * p23 % M) % M;
    
    delete []dp;

    return int(x);
}

• Subtask 1: 0 / 18
• Subtask 2: 0 / 31
• Subtask 3: 0 / 51