Submission #493457

#	Time	Username	Problem	Language	Result	Execution time	Memory
493457		Jeff12345121	Peru (RMI20_peru)	C++14	0 / 100	2 ms	340 KiB

peru

    #include <bits/stdc++.h>
    #define ll long long
    #include "peru.h"
    using namespace std;
     
     
     
    const int nmax = 400005;
    const ll inf = LLONG_MAX;
    const int P = 1000000007;
    ll v[nmax],dp[nmax];
    int solve(int n, int k, int* s) {
        for (int i = 1; i <= n; i++)
            v[i] = s[i - 1];
        for (int i = 1; i <= n; i++) dp[i] = inf;
        for (int i = 1; i <= n; i++) {
            ll maxSoFar = -1;
            for (int j = i - 1; j >= 0 && j >= i - k; j--) {
                maxSoFar = max(maxSoFar , v[j + 1]);
                dp[i] = min(dp[i] , dp[j] + maxSoFar);
            }
        }
     
        ll put23 = 1;
        int sum = 0;
        for (int i = n; i >= 1; i--) {
            sum = (1ll * sum + dp[i] * put23 % P) % P;
            put23 = ( put23 * 23 ) % P;
        }
      //  out << sum << "\n";
        return sum;
    }
    /*
    int main() {
        int s[nmax];
        int n = 8, k = 3;
        vector<int> vec = {3 ,2, 9, 8, 7, 11, 3, 4};
        for (int i = 0; i < n; i++) {
            s[i] = vec[i];
        }
        solve(8 , 3 , s);
    }*/

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