Charlinho challenge from http://codeforces.com/group/kZPk3ZTzR5/contest/101040/problem/I

charlinho.cpp

#include <iostream>
#include <cmath>
#include <climits>

using namespace std;

const int MAX_N = 510;
const int MAX_K = 510;

int N, K;
int C[MAX_N];

typedef struct elem {
  long long value;
  int last_idx;
} elem;

elem dp[MAX_N][MAX_K];

elem fazdp(int p, int q) {
  if (dp[p][q].value != -1) {
    return dp[p][q];
  }

  if (q == 0) {
    dp[p][q].value = LLONG_MIN;
    dp[p][q].last_idx = -1;
    return dp[p][q];
  }

  if (p == N - 1) {
    if (q == 1) {
      dp[p][q].value = C[p];
      dp[p][q].last_idx = -1;
    } else {
      dp[p][q].value = LLONG_MIN;
      dp[p][q].last_idx = -1;
    }

    return dp[p][q];
  }

  for(int j = p + 1; j <= N - 1; j++) {
    elem x = fazdp(j, q - 1);
    long long new_value = x.value + C[p] - fabs(C[p] - C[j]) * (j - p - 1);

    if (dp[p][q].value < new_value) {
      dp[p][q].value = new_value;
      dp[p][q].last_idx = j;
    }
  }

  return dp[p][q];
}

int main() {
  cin >> N >> K;

  for (int i = 0; i < N; i++) {
    for (int j = 0; j <= K; j++) {
      dp[i][j].value = -1;
      dp[i][j].last_idx = -1;
    }

    cin >> C[i];
  }

  long long resp = -1;
  int resp_idx = -1;
  for (int i = 0; i < N - 1; i++) {
    elem e = fazdp(i, K);
    if (resp < e.value) {
      resp = e.value;
      resp_idx = i;
    }
  }

  cout << resp << endl;

  int curr_k = K - 1;
  while (resp_idx != -1) {
    cout << resp_idx + 1 << " ";
    resp_idx = fazdp(resp_idx, curr_k + 1).last_idx;
    curr_k--;
  }

  cout << endl;

  return 0;
}

input

5 4
5 1 1 1 5