P3350.第2题-放他一马

1000ms

Difficulty: 6

所属公司 : 美团

算法与标签>动态规划

题目内容

小美会按照编号从小到大的顺序依次遇到 $n$ 只怪物（编号为 $1$ ~ $n$ ），怪物 $i(1 ≤ i ≤ n)$ 的生命为 $a_i$ 。

对于每只怪物，小美都可以选择放走 Ta 或者击败 Ta。

如果放走怪物，小美将获得 $i$ 点经验值。
如果击败怪物，小美将获得 $a_i$ 点经验值，同时将额外获得 ( $x$ $mod$ $10) × a_i$ 点经验值， $x$ 为击败怪物数量（包括这一个怪物）。

求小美最多可以从这 $n$ 个怪物中获得的经验值。

第一行输入一个整数 $n(1 ≤ n ≤ 2 × 10^5)$ 表示怪物数。

第二行输入 $n$ 个整数 $a_i(1 ≤ a_i ≤ 10^9)$ 表示怪物的生命。

输出一个整数表示小美可以获得最高的经验值。

输入

3
5 3 2

输出

说明

第一个怪物选择击败获得 $5+5×1= 10$ 的经验值，第二个怪物选择击败获得 $3+3×2= 9$ 的经验值，第三只怪物选择击败获得 $2+ 2×3=8$ 的经验值，总共获得 $27$ 的经验值。

输入

预期输出（选填）