Backup

input/code.cpp: In function 'int main()':
input/code.cpp:41:6: warning: unused variable 'edans' [-Wunused-variable]
  int edans = ans;
      ^~~~~
input/code.cpp:77:8: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
   z[b] = i;
   ~~~~~^~~
input/code.cpp:76:8: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]
   z[a] = i;
   ~~~~~^~~

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define N (1<<18)
#define M 1000000007
#define P complex<long long>
#define X real()
#define Y imag()

using namespace std;

int n, k, so[101010], s[101010], z[101010], ss[101010];
ll ans = 1e14;

void haku(int otettu, int nyk, ll sum) {
	if(otettu == k)
		ans=min(sum,ans);
	if(nyk >= n-1 || otettu == k)
		return;
	haku(otettu, nyk+1, sum);
	haku(otettu+1, nyk+2, sum+ss[nyk]);
}

int main() {
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	int T = 1;
	for(int g=0; g<T; g++) {
	ans = 1e14;
	cin >> n >> k;
	for(int i=0; i<n; i++) {
		cin >> s[i];
		so[i] = s[i];
		if(i)
			ss[i-1] = s[i]-s[i-1];
		z[i] = 0;
	}
//	haku(0,0,0);
	int edans = ans;
//	cout << ans << " ";
	ans = 1e14;
	for(int i=1; i<=k; i++) {
		int mini = 1e9+1;
		int a, b, oik;
		for(int j=0; j<n-1; j++) {
			int mod = 0;
			oik = j+1;
			if(z[j])
				continue;
			bool pal = false;
			int eee = 0;
			int aaa = j;
			while(z[oik]) {
				if(pal) {
					mod -= s[oik]-s[eee];
					aaa = oik;
				} else {
					mod += s[oik]-s[aaa];
					eee = oik;
				}
				pal = !pal;
				oik++;
			}
			mod += s[oik]-s[aaa];
			if(oik >= n) {
				continue;
			}
			if(mod < mini) {
				a = j;
				b = oik;
				mini = mod;
			}
		}
		z[a] = i;
		z[b] = i;
	}
	ans = 0;
	int ed = -1;
	for(int i=0; i<n; i++) {
		if(z[i]) {
			if(ed == -1) {
				ed = i;
			} else {
				ans += so[i]-so[ed];
				ed = -1;
			}
		}
	}
//	haku(0,0,0);
	cout << ans;
//	if(edans != ans)
//		cout << edans << " " << ans << endl;
	}
}

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