As our goal is to determine when Bessie should be subscribing to Mooloo, we begin by thinking about what optimal time periods for subscribing might look like. Our solution must involve Bessie subscribing for contiguous segments of days, as well as ranges where Bessie is unsubscribed in between these subscription segments.

Let us consider the gap between any two days $d_i$ and $d_{i+1}$ where Bessie must watch Mooloo. Bessie essentially has two choices:

• Bessie continues her subscription from $d_i$ to $d_{i+1}$. This means she will additionally pay $d_{i+1}-d_i-1$ moonies for the days in between.
• Bessie will cancel her subscription after $d_i$ and restart on day $d_{i+1}$. The cost of restarting a new subscription will be an additional $K$ moonies for Bessie.

Accordingly, Bessie can compare these two costs and choose the smaller one. Meaning, if the cost of the first option is smaller, she will continue her subscription between $d_i$ and $d_{i+1}$. Otherwise, she will cancel her subscription after day $d_i$ and restart on day $d_{i+1}$.

Given this strategy, we can iterate through the days and determine the total cost for Bessie in $O(n)$ time.

Spencer Compton's C++ code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main(){
    int N, K;
    cin >> N >> K;
    ll ans = 0LL;
    ll day[N];
    for(int i = 0; i<N; i++){
        cin >> day[i];
        if(i == 0){
            // It is the first day, I must start a new subscription
            ans += K + 1LL;
        }
        else{
            // Decide whether to extend a subscription, or end it and start a new one
            ll extendCost = day[i] - day[i-1];
            ll newCost = K + 1LL;
            ans += min(extendCost, newCost);
        }
    }
    cout << ans << endl;
}

Brandon Wang's Java code:

import java.util.*;
import java.io.*;
 
public class MoolooBronze {
	public static void main(String args[]) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	
		StringTokenizer tokenizer = new StringTokenizer(in.readLine());
		int N = Integer.parseInt(tokenizer.nextToken());
		long K = Long.parseLong(tokenizer.nextToken());
 
		long[] days = new long[N];
		tokenizer = new StringTokenizer(in.readLine());
 
		for (int i = 0; i < N; i++) {
			days[i] = Long.parseLong(tokenizer.nextToken());
		}
 
		long ans = K+1;
 
		for (int i = 1; i < N; i++) {
			ans += Math.min(K+1, days[i] - days[i-1]);
		}
 
		System.out.println(ans);
	}
}

Benjamin Qi's Python code:

N, K = map(int, input().split())
days = [int(x) for x in input().split()]
print(K + days[-1] - days[0] + 1 + sum(min(K - (d1 - d0 - 1), 0) for d0, d1 in zip(days, days[1:])))

Spencer Compton's Python code:

N, K = map(int, input().split())
days = [int(x) for x in input().split()]
ans = 0
for i in range(N):
    if i == 0:
        # It is the first day, I must start a new subscription
        ans += K + 1
    else:
        # Decide whether to extend a subscription, or end it and start a new one
        extendCost = days[i] - days[i-1]
        newCost = K + 1
        ans += min(extendCost, newCost)
print(ans)