Fence Repair (APCS 2021-11 Beginner)

Points 100 1.0s 256M

A farm has a fence of width \(n\); each panel has its own height \(h[1], h[2], \ldots, h[n]\).

Some panels were blown down (their height is \(0\)). The owner wants to repair them, but he has forgotten their original heights. To reduce cost, for each broken panel he fills it with the smaller of its left and right neighbours' heights. How much does it cost in total (the sum of the added heights)?

It is guaranteed that no two adjacent panels are both broken, and a broken panel may be at the boundary (in which case it has only one neighbour, and that neighbour's height is used).

Input

The input has two lines:

  • The first line contains a positive integer \(n\).
  • The second line contains \(n\) integers \(h[1], h[2], \ldots, h[n]\) separated by spaces.

Constraints

  • \(3 \le n \le 100\)
  • \(0 \le h[i] \le 100\)
  • No two adjacent panels are both broken (both \(0\))

Output

Output a single integer: the total added height.

Scoring

The time limit for each test case is \(1\) second; your score is the sum over the test cases you pass. The subtasks are:

  • Subtask 1 (\(60\) points): \(n = 3\).
  • Subtask 2 (\(40\) points): no additional constraints.

Sample Input 1

3
2 0 4

Sample Output 1

2

Sample Input 2

9
0 5 3 0 6 4 0 1 0

Sample Output 2

10

Source

APCS programming exam, November 2021, Problem 1.

Problem page help

Keyboard shortcuts

Main features

  • Sample tests — Runs the sample cases bundled with the problem and auto-compares against the expected output.
  • Custom test — Run your code with your own stdin. Optionally tick the "Compare with expected (diff)" box to verify against expected output line-by-line.
  • Template — Paste the default code template you set on your profile page.
  • Collab — Edit this problem together with classmates in real time.
  • Auto-draft — Editor contents auto-save to your browser every 1.5 seconds (per account / problem / language).
  • Submit — Send your code to the judge for grading; returns AC / WA / TLE etc.

Limits

  • Source code: at most 65,536 characters
  • Custom test stdin and expected output: at most 1 MB each (≈1 million characters)
  • Custom test and sample test share the sandbox; about 1 request per 3 s per user (sample test: 1 per 1 s)
  • Custom test and sample test both have a 15 second wall-clock cap (the official judge still uses the problem time limit)
  • Interactive problems do not offer custom test (cannot simulate interaction with the judge).
  • Submitting has no rate limit, but rapid repeated submissions on the same problem are treated as score farming.