Codeforces Round #210 (Div. 1)——Levko and Array

const int maxn = 2100;

int ipt[maxn], dp[maxn];
int n, k;

int check(LL Max)
{
    REP(i, n) dp[i] = i;
    REP(i, n) REP(j, i)
        if (abs(ipt[j] - ipt[i]) <= Max * (i - j))
            dp[i] = min(dp[i], dp[j] + i - j - 1);
    REP(i, n)
        if (dp[i] + n - i - 1 <= k)
            return true;
    return false;
}

int main()
{
    while (~RII(n, k))
    {
        REP(i, n)
            RI(ipt[i]);
        LL l = 0, r = 2e9, m;
        while (l <= r)
        {
            m = (l + r) >> 1;
            if (check(m))
                r = m - 1;
            else
                l = m + 1;
        }
        cout << l << endl;
    }
    return 0;
}