Backup

#include <iostream>

using namespace std;

const int N = 1e5 + 5;

int d[N];
int s[N];
int dp[N];
int mi[N];

int main() {
	int n, k;
	cin >> n >> k;
	for(int i = 1; i <= n; ++i) {
		cin >> s[i];
	}
	for(int i = 1; i < n; ++i) {
		d[i] = s[i+1] - s[i];
	}
	mi[n] = 1e9;

	for(int i = n-1; i >= 1; --i) {
		dp[i] = d[i];
		mi[i] = min(mi[i+1], dp[i]);
	}


	for(int i = 2; i <= k; ++i) {
		int newDP[N];
		for(int j = 1; j <= n-1; ++j) {
			newDP[j] = 1e9;
			if(j+2 <= n-1) {
				newDP[j] = mi[j+2] + d[j];
			}
		}
		for(int j = n-1; j >= 1; --j) {
			dp[j] = newDP[j];
			mi[j] = min(mi[j+1], dp[j]);
		}		
	}

	cout << mi[1] << "\n";

}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 4

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 2, 3

Verdict: ACCEPTED

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

Test 9

Group: 2, 3

Verdict: ACCEPTED

Test 10

Group: 2, 3

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 1, 2, 3

Verdict: ACCEPTED

Test 15

Group: 2, 3

Verdict: ACCEPTED

Test 16

Group: 3

Verdict: ACCEPTED

Test 17

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 18

Group: 2, 3

Verdict: ACCEPTED

Test 19

Group: 2, 3

Verdict: ACCEPTED

Test 20

Group: 3

Verdict: TIME LIMIT EXCEEDED