Submission #872595

#	Time	Username	Problem	Language	Result	Execution time	Memory
872595		sleepntsheep	Peru (RMI20_peru)	C++17	49 / 100	1010 ms	41292 KiB

peru

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

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

    void push(const T &v)
    {
        b.push(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);}
        int 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->front();
        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];

    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);

        if (dq.size() && dq.front() + k == i)
        {
            dq.pop_front();
            if (dq.size()) qry.pop_front();
        }

        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;
    for (size_t i = 0; i < n; ++i) x = (x * 23ll % M + dp[i]) % M;
    
    delete []dp;

    return int(x);
}

Compilation message (stderr)

peru.cpp: In function 'int solve(int, int, int*)':
peru.cpp:168:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  168 |     for (size_t i = 0; i < n; ++i) x = (x * 23ll % M + dp[i]) % M;
      |                        ~~^~~

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