We will discuss the solution to Discount Destinations from AIO 2026.
When K = 1, every group of K days
is just a single day, so the discount limits our spending on each individual day to D dollars.
On day i we pay the full fare Ai if we can afford it, and otherwise we pay D.
In other words, we pay the minimum of Ai and D.
We can loop over all the days and add these amounts to our answer.
For example, in sample input 1 we have D = 3 and the fares are 2, 4, 7, 1, 3. We pay 2, 3, 3, 1, 3, giving a total of 12 dollars. This solution has a time complexity of O(N).
If D ≥ K then we can pay 1 dollar every day without ever going over the limit, so the answer is N. The interesting case is when D < K. Let's try an example with N = 7, K = 3 and D = 2:
There is a pattern here! Every group of K days starts with D payments of 1 dollar, followed by K-D payments of 0 dollars, and then the pattern repeats. There are ⌊N/K⌋ complete groups, which each cost D dollars. There are also N % K days left over at the end, and we pay 1 dollar on each of the first D of these. The answer is therefore ⌊N/K⌋ × D + min(N % K, D) when D < K. In our example this gives 2 × 2 + min(1, 2) = 5, which matches.
For this subtask we will simulate the trip exactly as the problem describes. We process the days in order, storing the amount we actually pay on day i as Bi.
On day i, the last K days are today and the K-1 days before it. So before charging for today, we add up the payments on the previous K-1 days (or all previous days if there are fewer than K-1 of them). Let's call this sum S. We are allowed to pay at most D-S dollars today, and we never pay more than the fare, so Bi = min(Ai, D-S). Finally, we add up all the Bi to obtain the answer.
Let's look at sample input 2, where K = 3, D = 3 and the fares are 1, 2, 3, 2, 1:
| Day | Fare | Payments on the previous 2 days | S | We pay |
|---|---|---|---|---|
| 1 | 1 | none | 0 | min(1, 3-0) = 1 |
| 2 | 2 | 1 | 1 | min(2, 3-1) = 2 |
| 3 | 3 | 1, 2 | 3 | min(3, 3-3) = 0 |
| 4 | 2 | 2, 0 | 2 | min(2, 3-2) = 1 |
| 5 | 1 | 0, 1 | 1 | min(1, 3-1) = 1 |
The total is 1 + 2 + 0 + 1 + 1 = 5 dollars, which matches the sample output. Notice that on day 4 we add up the actual payments on days 2 and 3 (2 and 0), not the original fares (2 and 3). If we used the original fares we would think we couldn't pay anything on day 4, which is wrong.
Let's analyse the time complexity of this solution. Adding the previous payments takes O(K) time for each day, giving an overall time complexity of O(NK). This is fast enough to pass subtasks 1 and 3 but is not fast enough to solve the full problem.
Let's think about what the subtask 3 solution is doing. On day 4 of the example it adds up the payments on days 2 and 3. On day 5 it adds up the payments on days 3 and 4. Day 3 is added both times! In general, consecutive days add up almost exactly the same payments, and this repeated work is what makes our solution slow.
Instead, we can keep a running total of the recent payments and update it as we move from one day to the next.
When we move forward one day, one new payment enters the total and one old payment leaves it.
This technique is often called a sliding window, because the group of days we care about slides
along the trip one day at a time.
Specifically, we store a variable window, which contains the total of our last K payments. On day i:
The video below shows the window sliding along sample input 2.
Each day now takes O(1) time, so this solution has a time complexity of O(N) which is fast enough to score 100.
There are a few mistakes that are easy to make in this problem, so check that your code avoids all of them:
Below you can see the full solution written in Python and C++. I suggest trying to code the solution yourself and only look at our code after you finish or if you get stuck.
# N is the number of days.
N = 0
# K is the length of each group of days.
K = 0
# D is the most we can spend in any group of K days.
D = 0
# A contains the original fares. Note that the list starts from 0, and so the
# values are A[0] to A[N-1].
A = []
# Read the values of N, K, D, and the original fares.
N, K, D = map(int, input().strip().split())
A = list(map(int, input().strip().split()))
# B[i] will store the amount we actually pay on day i
B = [0] * N
# window stores the total of our last K payments
window = 0
# Compute the answer
answer = 0
for i in range(N):
if i >= K:
# The payment from K days ago no longer counts
window -= B[i-K]
# We pay as much of the fare as we can without going over D
B[i] = min(A[i], D - window)
window += B[i]
answer += B[i]
print(answer)
#include <cstdio>
#include <algorithm> // for std::min
/* N is the number of days. */
int N;
/* K is the length of each group of days. */
int K;
/* D is the most we can spend in any group of K days. */
int D;
/*
* A contains the original fares. Note that the array starts from 0, and so
* the values are A[0] to A[N-1].
*/
int A[200005];
/* B[i] will store the amount we actually pay on day i */
int B[200005];
int main(void) {
/* Read the values of N, K, D, and the original fares. */
scanf("%d%d%d", &N, &K, &D);
for (int i = 0; i < N; i++) {
scanf("%d", &A[i]);
}
/* Compute the answer */
int window = 0; // window stores the total of our last K payments
int answer = 0;
for (int i = 0; i < N; i++) {
if (i >= K) {
// The payment from K days ago no longer counts
window -= B[i-K];
}
// We pay as much of the fare as we can without going over D
B[i] = std::min(A[i], D - window);
window += B[i];
answer += B[i];
}
printf("%d\n", answer);
}