Submission #1217951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217951		RecursiveCo	Peru (RMI20_peru)	C++20	0 / 100	240 ms	29764 KiB

peru

#include "peru.h"
#include "queue"
#include "set"
using namespace std;

int mod = 1e9 + 7;

long long binpow(int base, int exp) {
    if (exp == 0) return 1;
    long long half = binpow(base, exp / 2);
    long long almost = half * half % mod;
    if (exp % 2) almost = almost * base % mod;
    return almost;
}

int solve(int n, int k, int* v){
    deque<int> q;
    int sum = 0;
    long long power = 1;
    for (int i = 0; i < n - 1; ++i) power = power * 23 % mod;
    vector<long long> dp(n);
    multiset<long long> ms;
    int inv = binpow(23, mod - 2);
    for (int i = 0; i < n; ++i) {
        while (!q.empty()) {
            int f = q.front();
            if (v[f] <= v[i]) {
                ms.extract((f? dp[f - 1]: 0) + v[f]);
                q.pop_front();
            } else {
                break;
            }   
        }
        if (!q.empty() && q.back() == i - k) {
            int b = q.back();
            ms.extract((b? dp[b - 1]: 0) + v[b]);
            q.pop_back();
        }
        ms.insert((i? dp[i - 1]: 0) + v[i]);
        dp[i] = min(*ms.begin(), (i? q.empty()? i < k? 0: dp[i - k]: dp[i - 1]: 0) + v[i]);
        q.push_front(i);
        long long here = dp[i] * power % mod;
        int cast_here = here;
        sum = (sum + cast_here) % mod;
        power = power * inv % mod;
    }
    return sum;
}

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