Submission #1297070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297070		efeg	Peru (RMI20_peru)	C++20	0 / 100	1097 ms	30944 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 + 10,1e18); 
    for (int i = 0; i < n; i++){
        if (i != 0) dp[i] = add(dp[i-1],v[i]); 
        i64 mx = 0; 
        for (int j = 0; j < k; j++){
            i64 old; 
            if (i - j - 1 < 0) old = 0;  
            else old = dp[i - j - 1]; 

            if (i - j > -1) mx = max(mx,(i64) v[i - j]); 
            dp[i] = min(dp[i],add(old,mx)); 
        }
        cerr << dp[i] << " "; 
    }
    cerr << endl; 

    i64 ans = 0,pw = 1;
    for (int i = n-1; i > -1; i--){
        ans = add(ans,mul(dp[i],pw)); 
        pw = mul(pw,23); 
    }

    for (int i = 0; i < n; i++) cerr << dp[i] << " ";


    return ans; 
}

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