Problem: Example

Input

1 10 2
1 1 1


Output

2.0

Solution (in CPP):

Solution:
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <numeric>

#define show(x) cerr << #x << " = " << x << endl

using namespace std;
using ll = long long;
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v)
{
    os << "sz:" << v.size() << "\n[";
    for (const auto& p : v) {
        os << p << ",";
    }
    os << "]\n";
    return os;
}

int main()
{
    int rp, max, K;
    cin >> rp >> max >> K;
    max -= rp;
    vector<int> T(K + 1);
    for (int i = 0; i <= K; i++) {
        cin >> T[i];
    }
    vector<vector<int>> dp(K + 1, vector<int>(max + 1, 0));
    for (int i = 0; i < K; i++) {
        dp[i][1] = T[0];
    }
    constexpr int INF = 1 << 30;
    vector<int> f(max + 1, INF);
    f[0] = 0;
    f[1] = 0;

    for (int j = 2; j <= max; j++) {
        for (int i = 1; i <= K; i++) {
            int mini = INF;
            for (int l = 1; l < j; l++) {
                mini = min(mini, dp[i - 1][j - l] + f[l] + l * T[i]);
            }
            dp[i][j] = mini;
            f[j] = min(f[j], mini);
        }
        dp[0][j] = f[j] + j * T[0];
    }
    cout << fixed << setprecision(15) << (long double)f[max] / max << endl;

    return 0;
}