Submission #1297029

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297029		m_a_d	Peru (RMI20_peru)	C++20	18 / 100	188 ms	327680 KiB

peru

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

using namespace std;

const long long MOD = 1e9+7;

int mod_expo(long long a, long long e) {
    if (e == 0) return 1;
    if (e == 1) return a % MOD;
    long long val = mod_expo(a/2, e);
    long long extra = (a % 2 == 1 ? a : 1);
    return (((val * val) % MOD) * extra) % MOD;
}

int32_t solve(int32_t n, int32_t k, int32_t* arr) {

    // long long everywhere it matters
    vector<long long> exponents(n);
    exponents[0] = 1;
    for(int i = 1; i < n; i++)
        exponents[i] = (exponents[i-1] * 23) % MOD;

    // dp uses long long, and initial value must be LLONG_MAX
    vector<vector<long long>> dp(n, vector<long long>(k, LLONG_MAX));

    dp[0][0] = arr[0];
    for(int j = 1; j < k; j++)
        dp[0][j] = max(dp[0][j-1], (long long)arr[j]);

    for(int i = 1; i < n; i++) {
        long long st_val = LLONG_MAX;

        for(int j = 0; j < k; j++) {
            if(i - 1 - j < 0) break;
            st_val = min(st_val, dp[i-1-j][j]);
        }

        long long add = arr[i];

        for(int j = 0; j < k; j++) {
            if(i + j >= n) break;
            add = max(add, (long long)arr[i+j]);
            dp[i][j] = st_val + add;   // no mod here!!
        }
    }

    vector<long long> ans(n, LLONG_MAX);

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < k; j++) {
            if(i - j < 0) break;
            ans[i] = min(ans[i], dp[i-j][j]);
        }
    }

    long long mod_ans = 0;
    for(int i = 0; i < n; i++) {
        mod_ans = (mod_ans + (ans[i] % MOD) * exponents[n - i - 1]) % MOD;
    }

    return mod_ans;
}

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