C_Road_Optimization.cpp

#include <bits/stdc++.h>
using namespace std;
// First you make it work, then you can always make it beautiful

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, l, k;
    cin >> n >> l >> k;

    vector<int> d(n + 1), a(n);

    for(int i=0;i<n;i++) cin >> d[i];
    for(int i=0;i<n;i++) cin >> a[i];
    d[n] = l;

    vector<vector<int>> dp(k + 1, vector<int>(n + 1));
    vector<vector<int>> dp2(k + 1, vector<int>(n + 1));

    for(int i=n-1;i>=0;i--) {
        for(int k1 = 0; k1 <= i; k1++) {
            for(int j=0;j<=k;j++) {
                int dist = d[i+1] - d[i];
                dp[j][k1] = dist * a[i] + dp2[j][i];
                if(j >= 1) {
                    dp[j][k1] = min(dp[j][k1], dist * a[k1] + dp2[j-1][k1]);
                }
            }
        }
        dp2 = dp;
    }

    cout << dp[k][0] << '\n';

    return 0;
}