We will discuss the solution to Sunday Drive II from AIO 2026.
If there were no volume limits at all, the best thing to do would be to increase the volume by 1 at the start of every kilometre. The volumes would be 1, 2, 3, and so on. In this subtask, all the limits except the last one are 10 000, and since N ≤ 1000 we can never get anywhere near this volume. So only the last kilometre's limit can stop us.
If the last kilometre has a small limit, we might need to start turning the volume down before we reach it. Suppose N = 5 and the final limit is V5 = 0:
These volumes never change by more than 1 between kilometres and never go over a limit, so this is a valid drive. Since no valid drive can ever be louder than either bound, this drive is also the best possible. We can compute the answer in O(N) time.
We can extend the same idea to this subtask.
Every kilometre with a limit of 0 forces the volume there to be 0.
If kilometre j has a limit of 0, then the volume on kilometre i can be at most |i-j|, since we can only change the volume by 1 per kilometre.
We can also think of the start of the street as kilometre 0
, with a volume of 0.
So for each kilometre i, the best volume is its distance to the closest of these zero-volume positions. For example, suppose N = 6 and only kilometre 3 has a limit of 0:
| Kilometre | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| Limit | 10 000 | 10 000 | 0 | 10 000 | 10 000 | 10 000 |
| Distance to the start | 1 | 2 | 3 | 4 | 5 | 6 |
| Distance to kilometre 3 | 2 | 1 | 0 | 1 | 2 | 3 |
| Volume | 1 | 1 | 0 | 1 | 2 | 3 |
This gives a total enjoyment of 8. Notice that there is no rule saying we have to finish at volume 0, so we shouldn't add a zero-volume position at the end of the street!
For each kilometre we can check every zero-volume position, which takes O(N) time. This gives an overall time complexity of O(N2), which is fast enough for this subtask.
What happens if the limits can be any value, not just 0 or 10 000? The same idea still works. The volume on kilometre j is at most Vj, and we can only change the volume by 1 per kilometre. Therefore the volume on kilometre i is at most Vj + |i-j|. Every kilometre j gives us one of these bounds, and the start of the street gives us the bound i as before.
For each kilometre i we find the smallest of all these bounds, and call it Bi. Our answer is B1 + B2 + ... + BN. As in the previous subtask, computing all the bounds takes O(N2) time.
For example, suppose the limits are 5, 5, 2, 5, 1, 5, 0. On kilometre 4, the limit of 1 on kilometre 5 gives the bound 1 + |4-5| = 2, and no other bound is smaller, so B4 = 2. Doing this for every kilometre gives 1, 2, 2, 2, 1, 1, 0, for a total of 9. The video below draws every bound and finds the smallest one on each kilometre.
It's clear that no valid drive can be louder than Bi on any kilometre. But is it actually possible to set the volume to Bi on every kilometre at once? It turns out that it is. Try to prove this yourself before reading my proof!
We need to check three things: the volumes don't break any limits, the first volume is at most 1, and consecutive volumes differ by at most 1.
The bound from kilometre i itself is Vi + 0 = Vi, so Bi ≤ Vi. The bound from the start of the street is 1 on kilometre 1, so B1 ≤ 1. Every bound is at least 0, so the volume never goes below 0 either.
Each individual bound changes by at most 1 between consecutive kilometres. Suppose some bound is the smallest one on kilometre i, so its value there is Bi. On kilometre i+1, that same bound is at most Bi + 1. Since Bi+1 is the smallest of all the bounds on kilometre i+1, we get Bi+1 ≤ Bi + 1. The same argument in the opposite direction gives Bi ≤ Bi+1 + 1. Therefore consecutive volumes differ by at most 1, so the drive is valid.
Since every valid drive must obey every bound, no valid drive can have a higher volume than Bi on any kilometre. Our drive is valid and reaches every bound, so it has the maximum possible total enjoyment.
We need to compute the same Bi values more quickly. The trick is to split the bounds into two groups: the bounds from limits to the left of kilometre i (including the start of the street), and the bounds from limits to the right of kilometre i. We can handle each group with one loop.
First, we go from left to right. We set B1 = min(V1, 1), and at every later kilometre we set Bi = min(Vi, Bi-1 + 1). Why does this work? Bi-1 already contains the smallest bound from everything up to and including kilometre i-1. All of these limits are one kilometre further away from kilometre i, so their bounds are all 1 higher, which is why we add 1. The only new limit is Vi itself.
Next, we go from right to left, using the same idea for the limits to our right. At each kilometre we replace Bi with min(Bi, Bi+1 + 1). After both loops, Bi contains the smallest bound from every limit on both sides, which is exactly the same value as in our subtask 3 solution.
Let's try this on the same example as before, where the limits are 5, 5, 2, 5, 1, 5, 0:
| Kilometre | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| Limit | 5 | 5 | 2 | 5 | 1 | 5 | 0 |
| After the left-to-right loop | 1 | 2 | 2 | 3 | 1 | 2 | 0 |
| After the right-to-left loop | 1 | 2 | 2 | 2 | 1 | 1 | 0 |
The answer is 1 + 2 + 2 + 2 + 1 + 1 + 0 = 9, which matches our subtask 3 solution. Notice that the first loop by itself is not enough. It increases the volume to 3 on kilometre 4, which is too loud to decrease to 1 in time for kilometre 5. It also leaves the volume at 2 on kilometre 6, which is too loud to decrease to 0 in time for kilometre 7. The second loop fixes both of these. As an exercise, try both loops on sample inputs 2 and 3 yourself. You should get the volumes 1, 2, 2, 1, 0 for a total of 6, and 1, 2, 2, 1, 2 for a total of 8.
The video below shows both loops on this example.
Each loop takes O(N) time, so this solution has a time complexity of O(N) which is fast enough to score 100.
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 length of the street in kilometres.
N = 0
# V contains the volume limits. Note that the list starts from 0, and so the
# values are V[0] to V[N-1].
V = []
# Read the value of N and the volume limits.
N = int(input().strip())
V = list(map(int, input().strip().split()))
# B[i] will store the best volume on kilometre i
B = [0] * N
# Left to right: include the starting volume and the limits to our left
B[0] = min(V[0], 1)
for i in range(1, N):
B[i] = min(V[i], B[i-1] + 1)
# Right to left: include the limits to our right
for i in range(N-2, -1, -1):
B[i] = min(B[i], B[i+1] + 1)
# Compute the answer
answer = sum(B)
print(answer)
#include <cstdio>
#include <algorithm> // for std::min
/* N is the length of the street in kilometres. */
int N;
/*
* V contains the volume limits. Note that the array starts from 0, and so the
* values are V[0] to V[N-1].
*/
int V[200005];
/* B[i] will store the best volume on kilometre i */
int B[200005];
int main(void) {
/* Read the value of N and the volume limits. */
scanf("%d", &N);
for (int i = 0; i < N; i++) {
scanf("%d", &V[i]);
}
/* Left to right: include the starting volume and the limits to our left */
B[0] = std::min(V[0], 1);
for (int i = 1; i < N; i++) {
B[i] = std::min(V[i], B[i-1] + 1);
}
/* Right to left: include the limits to our right */
for (int i = N-2; i >= 0; i--) {
B[i] = std::min(B[i], B[i+1] + 1);
}
/* Compute the answer */
int answer = 0;
for (int i = 0; i < N; i++) {
answer += B[i];
}
printf("%d\n", answer);
}