Codeforces Round #210 Div.2 D / Div.1 B - Levko and Array

cdf210_1b.cpp

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;

int main() {
  int N, K; cin >> N >> K;
  vector<int> a(N);

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

  ll left = -1, right = 2*(int)1e9;
  while (left + 1 < right) {
    ll mid = (left + right) >> 1;
    vector<int> dp(N, 1);
    bool ok = false;
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < i; j++) {
	if (abs(a[i] - a[j]) <= mid * (ll)(i - j)) {
	  dp[i] = max(dp[i], dp[j] + 1);
	}
      }
      if (N - dp[i] <= K) ok = true;
    }
    (ok ? right : left) = mid;
  }
  cout << right << endl;
  return 0;
}