USACO 2023 February Contest Bronze Division - Watching Mooloo

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

The main idea behind this problem is to observe that when we decide on whether to keep a subscription of not, we only care about the gap between the current day and the previous one.

Thereforf the gap between two consecutive days is greater than \(k\), we are better off by buying another subscription.

Source codes

The source codes in C++ and Python can be seen below.

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long n, k;
    cin >> n >> k;

    vector<long long> v(n+1);
    for(int i = 1; i <= n; i++)
        cin >> v[i];

    long long ans = k+1;
    for(int i = 2; i <= n; i++)
        ans += min(v[i] - v[i-1], k+1);

    cout << ans;
    return 0;
}

n, k = map(int, input().split())
v = list(map(int, input().split()))
ans = k + 1
for i in range(1, n):
    ans += min(v[i] - v[i - 1], k + 1)
print(ans)