Submission #1296992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296992		MisterReaper	Peru (RMI20_peru)	C++20	18 / 100	1096 ms	29832 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){
    std::vector<i64> f(N + 1, inf);
    f[0] = 0;
    for (int i = 1; i <= N; ++i) {
        int mx = 0;
        for (int j = i; j >= std::max(1, i - K + 1); --j) {
            mx = std::max(mx, A[j - 1]);
            f[i] = std::min(f[i], f[j - 1] + mx);
        }
    }

    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: 0 / 31
• Subtask 3: 0 / 51