Minimum Total Difficulty

[lolxxx]

Problem Statement

Virat is facing the deadly New Zealand bowlers and he has a plan for it. Each ball has a certain difficulty level represented by a value in an array 'a' of length 'n'. Virat aims to complete the innings while taking the minimum possible total difficulty.

However when facing a ball:
Virat can pass on the strike by taking a single for at most 'k' balls which adds 0 to the difficulty faced by him. But due to fatigue caused by running the subsequent balls have difficulty increased by 1.
Virat chooses a hit a boundary which adds the difficulty of the ball to difficulty faced by him.

Your goal is to help Virat by finding which balls to hit the boundaries so it minimizes the total difficulty, considering the ability to pass on the strike by taking a single. Print the minimum possible total difficulty achieved.

Example:

Input: 'n' = 7, 'k' = 5, 'a' = {8 ,2 , 5, 15, 11 , 2, 8}
Output: 9

For this test case, the balls that Virat should pass the strike to minimize the total difficulty are 1, 3, 4, 5,  and 7. This results in a total difficulty of 9, the minimum possible value.

To be precise, the total difficulty can be calculated as follows:
Ball 1 : Pass the Strike. (+1 to all subsequent balls)
Ball 2: Hit a Boundary. (Difficulty Face 2 + 1)
Ball 3: Pass the Strike. (+1 to all subsequent balls)
Ball 4: Pass the Strike. (+1 to all subsequent balls)
Ball 5: Pass the Strike. (+1 to all subsequent balls)
Ball 6: Hit a Boundary. (Difficulty Face 2 + 4)
Ball 7: Hit a Boundary. (Difficulty Face 2 + 1)
The total difficulty is thus 0 + 3 + 0 + 0 + 0 +6 + 0 = 9.

It can be proven that this is the optimal sequence, and there is no other way for Virat to complete the innings with a lower total difficulty.

Detailed explanation
Input Format:
The first line contains a single integer 't' denoting the number of test cases, then the test case follows.

For each test case, the first line will contain two spaced integers 'n' and 'n'.

The second line will contain 'n' spaced integers, i.e., the elements of the array 'a'.

Output Format:
For each test case, print the minimum possible total difficulty achieved.

The output for each test case should be on a new line.

Note: You are not required to print anything; it has already been taken care of. Just implement the function.

Sample Input 1:
2
5 5
1 2 3 4 5
4 1
5 10 11 5

Sample Output 1 :
0
21

Explanation For Sample Input 1:

For test case 1:
As we can pass the strike on all the balls the total difficulty is thus 0.

For test case 2:
In this test case, there are five possible ways to pass the strike some balls:

Do not pass the strike. Total difficulty: 5+10+11+5=31.
Pass the strike on the first ball. Total difficulty: 0 + (10+1) + (11+1) + (5+1) = 29.
Pass the strike on the second ball. Total difficulty: 5 + 0 + (11+1) + (5+1) = 23.
Pass the strike on the third ball. Total difficulty: 5 + 10 + 0 + (5+1) = 21.
Pass the strike on the fourth ball. Total difficulty: 5 + 10 + 11 + 0 = 26.

To minimize the total difficulty Virat should pass the strike on the third ball. Which results in a total difficulty of 21. Therefore, the answer is 21.

Sample Input 2:
2
7 5
8 2 5 15 11 2 8
6 3
1 2 3 4 5 6

Sample Output 2 :
9
6

Constraints:

1 ≤ T ≤ 10
1 ≤ N ≤ 10^5
0 ≤ K ≤ N
1 ≤ A[i] ≤ 10^9
It is guaranteed that the sum of 'N' is ≤ 10^5 over all test cases.

Time limit: 1 sec

Following are the test cases of the above question

Test case 1 input:
2
5 5
1 2 3 4 5
4 1
5 10 11 5
Desired Output:
0
21

Test case 2 input:
2
7 5
8 2 5 15 11 2 8
6 3
1 2 3 4 5 6
Desired Output:
9
6

Test case 3 input:
10
3 3
2 10 6
10 6
5 8 3 3 9 3 10 8 9 4
8 8
5 4 6 5 7 8 3 5
1 0
2
1 0
9
2 1
9 4
4 4
8 10 4 3
7 4
10 5 5 9 8 10 10
2 0
5 1
2 0
9 6
Desired output:
0
18
0
2
9
5
0
20
6
15

Test casse 4 input:
10
45 15
7 7 9 2 7 5 9 8 6 4 7 9 5 4 10 10 4 4 4 7 8 6 10 5 2 7 2 3 10 5 9 3 5 6 8 7 4 1 1 3 2 10 7 2 2
11 6
1 10 9 5 9 6 1 3 4 9 7
19 9
4 3 1 4 10 2 8 6 5 5 10 3 10 2 8 7 1 5 6
26 17
1 3 2 10 8 6 8 10 3 6 4 1 5 9 7 8 10 1 3 6 6 2 6 6 3 5
8 5
6 3 8 4 2 6 10 4
14 11
3 9 1 9 9 7 6 9 4 8 7 7 5 9
31 1
8 2 3 2 10 9 7 1 9 2 7 3 3 8 2 1 2 1 6 4 3 4 7 9 3 1 2 10 5 9 8
41 37
9 1 10 6 9 4 9 2 9 8 5 1 4 9 5 10 4 6 6 6 7 9 10 8 5 2 10 10 8 10 9 7 6 8 4 10 5 6 5 1 1
31 1
2 2 4 3 7 4 8 8 6 7 9 5 9 2 7 5 1 1 3 7 7 7 10 6 6 7 2 2 4 2 3
33 1
6 10 7 10 4 8 5 7 4 1 6 4 3 10 7 4 4 10 2 7 6 4 5 5 9 3 5 8 1 9 9 3 4
Desired output:
182
27
48
46
13
13
143
23
153
183

Test case 5 input:
10
18 5
24 10 65 1 36 24 29 99 31 22 99 49 90 99 6 55 61 16
47 19
28 42 46 11 92 33 7 66 67 80 53 47 24 85 1 62 39 14 66 78 83 24 86 15 89 50 8 11 36 17 66 28 57 23 44 14 25 34 12 97 36 51 84 16 96 86 57
25 20
20 73 79 70 38 48 56 94 55 10 87 91 37 36 57 79 76 3 6 52 48 53 74 93 88
25 6
73 78 94 13 5 25 47 1 55 37 60 40 56 1 36 39 44 47 83 34 42 16 96 32 5
19 11
70 77 93 6 34 59 4 41 57 96 13 34 97 7 3 28 42 73 9
40 19
84 31 19 57 52 91 12 52 25 7 91 93 53 1 73 71 33 88 20 84 73 61 63 7 1 66 56 8 73 58 92 71 82 50 52 88 66 73 85 50
42 22
32 23 76 1 20 8 16 95 93 13 76 72 15 19 22 2 82 84 6 52 79 67 40 74 54 96 7 99 5 58 93 8 61 7 23 19 44 88 31 4 15 30
18 14
13 81 62 94 39 19 13 63 33 34 74 57 69 89 16 63 3 32
7 2
77 67 34 34 83 77 14
3 0
61 37 12
Desired output:
385
957
115
651
159
843
441
69
228
110

Following is my Python code:

def findMinimumDifficulty(n: int, k: int, a: List[int]) -> int:
    # write your code here
    if n==k:
        return 0
    memo = {} 
    def backtrack(i, remaining_k, accumulated_sum, consecutive_count):
        if (i, remaining_k, accumulated_sum, consecutive_count) in memo:
            return memo[(i, remaining_k, accumulated_sum, consecutive_count)]
        if remaining_k == 0:
            return accumulated_sum
       
        elif i >= n:
            return 999999
       
        current_diff = backtrack(i + 1, remaining_k - 1, accumulated_sum + a[i] + consecutive_count, consecutive_count)
        next_diff = backtrack(i + 1, remaining_k, accumulated_sum, consecutive_count + 1)
       
        memo[(i, remaining_k, accumulated_sum, consecutive_count)] = min(current_diff, next_diff)
        return memo[(i, remaining_k, accumulated_sum, consecutive_count)]
   
    return backtrack(0, n - k, 0, 0)

It pass all the above cases. But it don't able to pass hidden test cases. And I got "TIME LIMIT EXCEED" Error.
How should I optimize the code?

Or if you have new solution. That solution is also welcome.