oj.uz

Submission #872591

# Submission time Handle Problem Language Result Execution time Memory
872591 2023-11-13T12:11:08 Z sleepntsheep Peru (RMI20_peru) C++17
0 / 100
 1 ms 348 KB 
#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;

    std::deque<int> dq;
    deque<i64, std::min> qry;

    for (int i = 0; i < k; ++i)
    {
        while (dq.size() && v[dq.back()] < v[i])
        {
            dq.pop_back();
            if (dq.size()) qry.pop_back();
        }
        if (dq.size()) qry.push_back(dp[dq.back()] + v[i]);
        dq.push_back(i);
        dp[i] = v[dq.front()];
    }

    for (int i = k; i < n; ++i)
    {
        while (dq.size() && v[dq.back()] <= v[i])
        {
            dq.pop_back();
            if (dq.size())
                qry.pop_back();
        }

        if (dq.size())
        {
            qry.push_back(dp[dq.back()] + v[i]);
            dq.push_back(i);
        }
        else
            dq.push_back(i);

        while (dq.size() && dq.front() + k - 1 < i)
        {
            dq.pop_front();
            if (dq.size())
                qry.pop_front();
        }

        dp[i] = std::min({dp[i], dp[i-k] + v[dq.front()]});
        if (qry.size()) dp[i] = std::min(dp[i], qry.op());
    }

    //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 (i64 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 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

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

Subtask #3
0 / 51.0

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