Table of Contents

ExplanationImplementation

Official Analysis (C++, Java, Python)

Explanation

We solve this problem with a greedy algorithm.

First, we iterate through all the days. On the first day, Bessie will always have to buy a new subscription. However, on subsequent days, there's two cases:

  1. It's better to extend the last subscription. This occurs when the cost of extending the last subscription, calculated by subtracting the date of the last one from the current day, is less than KK.
  2. If the previous condition isn't met, it's better to start a new subscription entirely.

Implementation

Time Complexity: O(N)\mathcal{O}(N)

C++

#include <bits/stdc++.h>
using namespace std;


int main() {
	int n;
	int k;
	cin >> n >> k;


	vector<long long> days(n);
	for (long long &d : days) { cin >> d; }

Java

import java.io.*;
import java.util.*;


public class WatchingMooloo {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().split(" ");
		int n = Integer.parseInt(input[0]);
		int k = Integer.parseInt(input[1]);

Python

n, k = map(int, input().split())
days = list(map(int, input().split()))


last_day = days[0]
cost = k + 1  # Start the first subscription


for d in days:
	# Should Bessie extend the most recent subscription?
	if d - last_day < k + 1:
		cost += d - last_day

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum