oj.uz

Submission #872495

# Submission time Handle Problem Language Result Execution time Memory
872495 2023-11-13T08:11:25 Z sleepntsheep Peru (RMI20_peru) C++17
0 / 100
 1 ms 344 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -