Submission #1295931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295931		jahongir	Peru (RMI20_peru)	C++20	0 / 100	1096 ms	29936 KiB

peru

#include "peru.h"

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mod = 1e9+7;

int solve(int N, int K, int* S){
    vector<ll> dp(N,0);
    dp[0] = S[0];

    for(int i = 1; i < N; i++){
        int mx = S[i];
        dp[i] = dp[i-1]+mx;
        for(int j = i-1; j >= 0 && i-j <= K; j--){
            dp[i] = min(dp[i],dp[j] + mx);
            mx = max(mx,S[j]);
        }
        if(i < K) dp[i] = mx;
    }

    int mtp = 1, ans = 0;
    for(int i = N-1; i >= 0; i--){
        ans += 1ll*dp[i]*mtp%mod;
        if(ans >= mod) ans -= mod;
        mtp = 1ll*mtp*23%mod;
    }

    return ans;
}

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