← 返回题目列表

AtCoder · abc275_h

Ex. 怪物

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

有 N 数轴上的怪物。在坐标处 i (1\leq i\leq N) 是一个耐力为 A_i.
另外,在坐标处 i,有一个强度的永久护盾 B_i.
即使同一坐标的怪物的生命值为 0 或以下。

高桥,一名魔术师,可以执行任意次数的以下操作。

  • 选择整数 l 和 r 满意 1\leq l\leq r\leq N.
  • 然后,消费 \max(B_l, B_{l+1}, \ldots, B_r) MP(魔法点)减少 1 坐标处每个怪物的体力 l,l+1,\ldots,r.

选择时 l 和 r,如果坐标处有一些怪物就好了 l,l+1,\ldots,r 已经有耐力 0 或以下。
但请注意,所有这些坐标处的护盾仍然存在。

高桥想要提高每个怪物的耐力 0 或以下。
找出实现目标所需的最低总 MP 数。

约束

  • 1 \leq N \leq 10^5
  • 1 \leq A_i,B_i \leq 10^9
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N

输出

打印实现其目标所需的最低 MP 总量。


示例输入 1

5
4 3 5 1 2
10 40 20 60 50

示例输出 1

210

高桥可以通过以下方式实现他的目标。

  • 选择 (l,r)=(1,5)。消费 \max(10,40,20,60,50)=60 MP,怪物的体力为 (3,2,4,0,1).
  • 选择 (l,r)=(1,5)。消费 \max(10,40,20,60,50)=60 MP,怪物的体力为 (2,1,3,-1,0).
  • 选择 (l,r)=(1,3)。消费 \max(10,40,20)=40 MP,怪物的体力为 (1,0,2,-1,0).
  • 选择 (l,r)=(1,1)。消费 \max(10)=10 MP,怪物的体力为 (0,0,2,-1,0).
  • 选择 (l,r)=(3,3)。消费 \max(20)=20 MP,怪物的体力为 (0,0,1,-1,0).
  • 选择 (l,r)=(3,3)。消费 \max(20)=20 MP,怪物的体力为 (0,0,0,-1,0).

在这里,他总共消耗了 60+60+40+10+20+20=210 MP,这是可能的最小值。


示例输入 2

1
1000000000
1000000000

示例输出 2

1000000000000000000

示例输入 3

10
522 4575 6426 9445 8772 81 3447 629 3497 7202
7775 4325 3982 4784 8417 2156 1932 5902 5728 8537

示例输出 3

77917796