Submission #857620

#	Time	Username	Problem	Language	Result	Execution time	Memory
857620		boris_mihov	Peru (RMI20_peru)	C++17	18 / 100	684 ms	17240 KiB

peru

#include "peru.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 2500000 + 10;
const int MOD = 1e9 + 7;
const llong INF = 1e18;
const int INTINF = 1e9;

int n, k;
int a[MAXN];
llong dp[MAXN];
int solve(int N, int K, int* v)
{
    n = N; k = K;
    for (int i = 1 ; i <= n ; ++i)
    {
        a[i] = v[i - 1];
    }

    dp[0] = 0;
    for (int i = 1 ; i <= n ; ++i)
    {
        int max = 0;
        dp[i] = INF;
        for (int j = 1 ; j <= std::min(i, k) ; ++j)
        {
            max = std::max(max, a[i - j + 1]);
            dp[i] = std::min(dp[i], dp[i - j] + max);
        }
    }

    int ans = 0;
    for (int i = 1 ; i <= n ; ++i)
    {
        ans = (1LL * ans * 23 + dp[i]) % MOD;
    }

    return ans;
}

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