Submission #493453

#	Time	Username	Problem	Language	Result	Execution time	Memory
493453		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 int 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;
        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