oj.uz

Submission #872562

# Submission time Handle Problem Language Result Execution time Memory
872562 2023-11-13T11:21:38 Z sleepntsheep Peru (RMI20_peru) C++17
0 / 100
 0 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);}
};

#if 1
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();
    }
};

#else
template <typename T, const T& (*F)(const T&, const T&)>
struct deque : std::deque<T>
{
    T op()
    {
        T x = (*this)[0];
        for (auto y : *this) x = F(x, y);
        return x;
    }
};
#endif

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, i64>, std::min> dq;


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

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

        /*
        assert(dq.size());
        int pb = std::max(i-k * 1ll, dq.size() ? std::get<1>(dq.back()) : -1ll);
        */

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

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

    }

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

    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 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

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

Subtask #3
0 / 51.0

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