gCFm2f - Online C++0x Compiler & Debugging Tool

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const long long INF = 1e18;

long long solve(int N, int K, int L, int R, vector<int>& a) {
    // dp[i][j] = min cost to partition first i elements into j groups
    vector<vector<long long>> dp(N + 1, vector<long long>(K + 1, INF));

    dp[0][0] = 0;

    for (int j = 1; j <= K; ++j) {
        for (int i = 1; i <= N; ++i) {
            int current_max = -1e9 - 7;
            int current_min = 1e9 + 7;

            // Try all possible lengths for the j-th group ending at i
            // The group starts at index i - len and ends at i - 1
            for (int len = 1; len <= min(i, R); ++len) {
                int val = a[i - len];
                current_max = max(current_max, val);
                current_min = min(current_min, val);

                if (len >= L && dp[i - len][j - 1] != INF) {
                    dp[i][j] = min(dp[i][j], dp[i - len][j - 1] + (current_max - current_min));
                }
            }
        }
    }

    return dp[N][K];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K, L, R;
    if (!(cin >> N >> K >> L >> R)) return 0;

    vector<int> a(N);
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }

    cout << solve(N, K, L, R, a) << endl;

    return 0;
}