Submission #1963680

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
using namespace std;

typedef long long ll;

ll N, M, K;


ll dp[20010];

// ll rec(int l,int r,Segment& seg)
// {
//     if(r <= l) return 1145141919810LL;

//     if(dp[l][r] != -1) return dp[l][r];

//     ll result = 1145141919810LL;

//     if(r - l <= M) result = min(result,K + (r - l) *(seg.getmax(l,r) - seg.getmin(l,r)));

//     for(int m = l + 1;m <= r - 1;m++)
//     {
//         result = min(result , rec(l,m,seg) + rec(m,r,seg));
//     }

//     return (dp[l][r] = result);
// }

vector<ll> A;

ll rec(int index)
{

    if(dp[index] != -1) return dp[index];

    if(index == N) return 0;

    ll result = 1e18;

    ll MAX = A[index];
    ll MIN = A[index];

    for(int next = index;next < min(index + M,N);next++)
    {
        MAX = max(MAX,A[next]);
        MIN = min(MIN,A[next]);
        result = min(result , rec(next + 1) + (1 + next - index) * (MAX - MIN) + K);
    }
    dp[index] = result;
    return result;

}

int main()
{
    for (int j = 0; j < 20010; j++)
    {
        dp[j] = -1;
    }

    cin >> N >> M >> K;
    A.resize(N);
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }

    cout << rec(0) << endl;
    return 0;
}

Submission Info

Judge Result