제출 #1296982

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1296982		MisterReaper	Peru (RMI20_peru)	C++20	18 / 100	366 ms	327680 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 SparseTable {
        int n;
        std::vector<int> logs;
        std::vector<std::vector<int>> mat;
        std::vector<int> v;
        SparseTable(int n_, int* v_) : n(n_), v(n) {
            for (int i = 0; i < n ; ++i) {
                v[i] = v_[i];
            }
            init();
        }
        void init() {
            logs.resize(n + 1, -1);
            for (int i = 1; i <= n; ++i) {
                logs[i] = logs[i >> 1] + 1;
            }

            int LG = logs[n];
            mat.resize(LG + 1);
            mat[0].resize(n);
            for (int i = 0; i < n; ++i) {
                mat[0][i] = i;
            }
            for (int i = 1; i <= LG; ++i) {
                mat[i].resize(n - (1 << i) + 1);
                for (int j = 0; j < n - (1 << i) + 1; ++j) {
                    mat[i][j] = std::min(mat[i - 1][j], mat[i - 1][j + (1 << (i - 1))], [&](auto lhs, auto rhs) {
                        return v[lhs] > v[rhs];
                    });
                }
            }
        }
        int get(int l, int r) {
            int len = r - l + 1;
            int lg = logs[len];
            return std::min(mat[lg][l], mat[lg][r - (1 << lg) + 1], [&](auto lhs, auto rhs) {
                return v[lhs] > v[rhs];
            });
        }
    };
};

int solve(int N, int K, int* A){
    SparseTable st(N, A);

    std::vector<std::vector<i64>> f(N, std::vector<i64>(N, -1));
    auto dfs = [&](auto&& self, int l, int r) -> i64 {
        if (l > r) {
            return 0;
        }
        if (r - l + 1 <= K) {
            int p = st.get(l, r);
            return A[p];
        }
        if (f[l][r] != -1) {
            return f[l][r];
        }
        i64 res = inf;
        int p = st.get(l, r);
        debug(l, r, p);
        for (int i = std::max(l, p - K + 1); i <= std::min(r - K + 1, p); ++i) {
            res = std::min(res, self(self, l, i - 1) + self(self, i + K, r) + A[p]);
        }
        return f[l][r] = res;
    };

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

    return ans;
}

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