제출 #1297113

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1297113		efeg	Peru (RMI20_peru)	C++20	0 / 100	1097 ms	31124 KiB

peru

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

using i64 = long long; 

const int MOD = 1e9 + 7; 

i64 add(i64 x,i64 y){
    return (x % MOD + y % MOD) % MOD; 
}
i64 mul(i64 x,i64 y){
    return (x % MOD * (y % MOD)) % MOD; 
}

int solve(int n, int k, int* v){
    vector<i64> dp(n + 1,2e18);
    
    dp[0] = v[0]; 
    for (int i = 1; i < k; i++){
        dp[i] = max(dp[i-1],(i64) v[i]); 
    }

    for (int i = k; i < n; i++){
        i64 mx = v[i]; 
        for (int j = i-1; j >= max(i - k,0); j--){
            dp[i] = min(dp[i], add(dp[j],mx)); 
            mx = max(mx,(i64) v[j]); 
        }
        cerr << dp[i] << " "; 
    }

    vector<i64> pw(n + 10); 
    pw[0] = 1; 
    for (int i = 1; i <= n; i++){
        pw[i] = (pw[i-1] * 23) % MOD; 
    }
    int ans = 0; 

    for (int i = 0; i < n; i++){
        dp[i] %= MOD; 
        i64 val = (dp[i] * pw[n - i - 1]) % MOD; 
        ans = (ans + val) % MOD; 
    }

    return ans; 
}

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