Submission #872495

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

peru

#include "peru.h"
#include <iostream>
#include <algorithm>
#include <stack>

template <typename T>
struct max_stack
{
    std::stack<T> a, b;

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

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

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

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

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

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

template <typename T>
struct max_deque
{
    max_stack<T> f, b;

    max_deque()
    {
    }

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

    void pop_front()
    {
        if (f.empty())
        {
            for (size_t i = 0; i < (b.size() + 1) / 2; ++i)
            {
                f.push(b.top());
                b.pop();
            }
        }
    }

    T max()
    {
        if (f.empty()) return b.max();
        if (b.empty()) return f.max();
        return std::max(f.max(), b.max());
    }
};

using u64 = long long;

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

    max_deque<int> dq;
    for (int i = 0; i < n; ++i)
    {
        if (i >= k) dq.pop_front();
        dq.push_back(v[i]);
        dp[i] = dq.max() + (i >= k ? dp[i-k] : 0);
    }

    constexpr u64 M = 1000000007;
    u64 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