#2147. Real Mountains

    ID: 2147 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 提高 上传者: 标签>TEAM赛事:contest1270来源:qoj.ac数据:公开样例二分答案贪心

Real Mountains

Real Mountains

题目描述

2023 Canadian Computing Olympiad Day 1, Problem 2 Real Mountains Time Limit: 5 seconds Problem Description Thanks to your help with cropping her picture, Rebecca’s scenic photo is now featured on the front cover of the newest issue of her magazine. However, it seems that some of her readers still aren’t pleased with the picture. In particular, they seem to believe that the mountain in the picture is fake! For simplicity, we can describe the picture as a sequence of N columns of pixels. In the i-th column, the first hi pixels from the bottom are of mountains. Her readers will only believe that the picture contains a real mountain if it contains a single (possibly wide) peak. That is, if there exists some index p with 1 ≤p ≤N such that h1 ≤h2 ≤· · · ≤hp ≥· · · ≥ hN−1 ≥hN. Luckily, Rebecca can still pay her editors to modify the picture and reprint the magazine. Unfortunately for her though, the editors have a very peculiar pricing scheme for their work. The only way Rebecca can edit the picture is by sending emails to her editors containing the integers (i, j, k) such that 1 ≤i < j < k ≤N and hi > hj < hk. The editors will then add an extra pixel of mountains in the j-th column (i.e. increment hj by 1) for a cost of hi + hj + hk cents. Note that the change in hj may affect the costs of future edits. To please her readers, Rebecca would like to edit the picture so that they believe it contains a real mountain. Can you tell her the minimum cost required to do so? Input Specification The first line of input contains an integer N. The second line of input contains N space-separated integers h1, h2, . . . , hN. Marks Awarded Bounds on N Bounds and constraints on hi 3 ≤N ≤5 000 1 ≤hi ≤100; 3 marks h1 ≥h2 ≥· · · ≥hp ≤· · · ≤hN−1 ≤hN for some p, 1 ≤p ≤N 3 ≤N ≤5 000 1 ≤hi ≤100 3 marks 1 ≤hi ≤106 3 ≤N ≤5 000 3 marks 1 ≤hi ≤109 3 ≤N ≤5 000 3 marks 3 ≤N ≤106 1 ≤hi ≤100 4 marks 3 ≤N ≤106 1 ≤hi ≤106 5 marks 3 ≤N ≤106 1 ≤hi ≤109 4 marks Output Specification Output the remainder of T divided by the prime number 106 + 3 where T is the minimum cost (in cents) that Rebecca would need to incur in order to please her readers. Sample Input 8 3 2 4 5 4 1 2 1 Output for Sample Input 14 Explanation of Output for Sample Input Rebecca can send two emails, the first containing the integers (2, 6, 7) and the second con- taining the integers (1, 2, 5). The first email costs 5 cents and increases h6 by 1, while the second email costs 9 cents and increases h2 by 1. The hi values in the final picture will be [3, 3, 4, 5, 4, 2, 2, 1]. Her readers will believe this final picture contains a real mountain.

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

8
3 2 4 5 4 1 2 1
14