Submission #1297148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297148		MisterReaper	Peru (RMI20_peru)	C++20	100 / 100	98 ms	32176 KiB

peru

#include "peru.h"
#include "bits/stdc++.h"

namespace {
    #ifdef DEBUG 
        #include "/home/ahmetalp/Desktop/Workplace/debug.h"
    #else
        #define debug(...) void(23)
    #endif

    using i64 = long long;

    constexpr i64 inf = i64(1E18);
    constexpr int md = int(1E9) + 7;

    struct mindeque {
        std::vector<std::pair<i64, i64>> lhs;
        std::vector<std::pair<i64, i64>> rhs;
        void balance_l() {
            int n = int(rhs.size());
            std::vector<i64> vv;
            for (int k = 0; k < n / 2; ++k) {
                vv.emplace_back(rhs.back().first);
                rhs.pop_back();
            }
            for (int k = 0; k < (n + 1) / 2; ++k) {
                emplace_front(rhs.back().first);
                rhs.pop_back();
            }
            for (int k = 0; k < n / 2; ++k){
                emplace_back(vv.back());
                vv.pop_back();
            }
        }
        void balance_r() {
            int n = int(lhs.size());
            std::vector<i64> vv;
            for (int k = 0; k < n / 2; ++k) {
                vv.emplace_back(lhs.back().first);
                lhs.pop_back();
            }
            for (int k = 0; k < (n + 1) / 2; ++k) {
                emplace_back(lhs.back().first);
                lhs.pop_back();
            }
            for (int k = 0; k < n / 2; ++k){
                emplace_front(vv.back());
                vv.pop_back();
            }
        }
        void emplace_front(i64 x) {
            lhs.emplace_back(x, std::min(lhs.empty() ? inf : lhs.back().second, x));
        }
        void emplace_back(i64 x) {
            rhs.emplace_back(x, std::min(rhs.empty() ? inf : rhs.back().second, x));
        }
        void pop_back() {
            if (rhs.empty()) {
                balance_r();
            }
            rhs.pop_back();
        }
        void pop_front() {
            if (lhs.empty()) {
                balance_l();
            }
            lhs.pop_back();
        }
        i64 min() {
            i64 res = inf;
            if (!lhs.empty()) {
                res = std::min(res, lhs.back().second);
            }
            if (!rhs.empty()) {
                res = std::min(res, rhs.back().second);
            }
            return res;
        }
    };
};

int solve(int N, int K, int* A) {
    std::vector<i64> f(N + 1, inf);
    std::deque<int> deq;
    f[0] = 0;
    mindeque mindeq;
    for (int i = 1; i <= N; ++i) {
        if (!deq.empty() && deq.front() == i - K - 1) {
            mindeq.pop_front();
            deq.pop_front();
        }
        while (!deq.empty() && A[deq.back() - 1] <= A[i - 1]) {
            mindeq.pop_back();
            deq.pop_back();
        }
        if (!deq.empty()) {
            mindeq.pop_back();
            mindeq.emplace_back(f[deq.back()] + A[i - 1]);
        }
        deq.emplace_back(i);
        debug(i, deq);
        f[i] = mindeq.min();
        f[i] = std::min(f[i], f[std::max(0, i - K)] + A[deq.front() - 1]);
        mindeq.emplace_back(f[i]);
        #ifdef LOCAL
            int mx = 0;
            i64 real = inf;
            for (int j = i; j >= std::max(1, i - K + 1); --j) {
                mx = std::max(mx, A[j - 1]);
                real = std::min(real, f[j - 1] + mx);
            }
            mx = 0;
            for (int j = i; j >= std::max(1, i - K + 1); --j) {
                mx = std::max(mx, A[j - 1]);
                real = std::min(real, f[j - 1] + mx);
                if (real == f[j - 1] + mx) {
                    debug(i, j - 1);
                }
            }
            debug(real, f[i]);
            assert(real == f[i]);
        #endif
    }

    int ans = 0;
    for (int i = 0; i < N; ++i) {
        int x = f[i + 1] % md;
        debug(i, x);
        ans = (ans * 23LL + x) % md;
    }

    return ans;
}

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