제출 #1217954

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1217954		KindaGoodGames	Peru (RMI20_peru)	C++20	18 / 100	1097 ms	49492 KiB

peru

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

using namespace std;

int INF = numeric_limits<int>::max()/2;
int mod = 1e9+7;

int exp(int a, int k){
    if(k == 0) return 1;
    int res = exp(a,k/2);

    if(k % 2 == 0) return (res * res) % mod;
    return ((res*res% mod) * a )% mod;
}

int32_t solve(int32_t n, int32_t k, int32_t* S){
    vector<int> v(n);
    for(int i = 0; i < n; i++){
        v[i] = S[i];
    }
    vector<int> dp(n+1, INF);

    dp[0] = 0;

    int res = 0;

    for(int i = 1; i <= n; i++){
        int ma = 0;
        for(int p = i; p >= max(1LL, i-k+1LL); p--){
            ma = max(ma, v[p-1]);
            dp[i] = min(dp[i], dp[p-1]+ma);
        }
        res += ((dp[i]%mod) * exp(23, n-i))%mod;
        res %= mod;
    }
    return res;
}

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