A row of n signal beacons lines a channel, numbered 0 to n-1. Beacon i has a strength a[i], which also doubles as its reach: it illuminates every beacon from index i - a[i] to index i + a[i], clipped at both ends to stay within 0 and n-1. The measured coverage contributed by beacon i is the sum of the strengths of every beacon inside its own clipped window (including itself). The total channel coverage is the sum of the coverage contributed by every beacon (a beacon inside several windows is counted once per window it falls in). Compute the total channel coverage.
n, the number of beacons.n space-separated integers a[0] a[1] ... a[n-1], the strength of each beacon.A single integer: the total channel coverage.
Example 1
Input
4 3 0 1 2
Expected
12
Explanation
a=[3,0,1,2]. Beacon 0 (reach 3) covers the whole array [0,3], contributing 3+0+1+2=6. Beacon 1 (reach 0) covers only itself, contributing 0. Beacon 2 (reach 1) covers [1,3], contributing 0+1+2=3. Beacon 3 (reach 2, clipped) covers [1,3], contributing 0+1+2=3. Total = 6+0+3+3 = 12.
Example 2
Input
3 2 1 3
Expected
18
Explanation
a=[2,1,3]. Beacon 0 (reach 2, clipped) covers [0,2], the whole array: 2+1+3=6. Beacon 1 (reach 1) also covers [0,2]: 6. Beacon 2 (reach 3, clipped) also covers [0,2]: 6. Total = 6+6+6 = 18.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →