← 返回题目列表

AtCoder · abc201_f

F. 插入排序

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

分数: 600 点

问题陈述

有 N 已获得 ID 号的人 1 通过 N,从左到右站成一排。最初,身份证号码 i左起第一个人是 P_i.

你的目标是通过重复执行以下三种操作,将人员按照 ID 号从左到右升序重新排列。您可以以任何顺序执行这些操作任意次数(可能为零)。

  • 选择一个整数 i\ (1 \leq i \leq N),支付费用 A_i,并移动人 i (身份证号码为 i) 到您选择的任何位置。
  • 选择一个整数 i\ (1 \leq i \leq N),支付费用 B_i,并移动人 i 到行的左端。
  • 选择一个整数 i\ (1 \leq i \leq N),支付费用 C_i,并移动人 i 到行的右端。

最大限度地减少实现目标之前支付的总成本。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq P_i \leq N
  • 1 \leq A_i,B_i,C_i \leq 10^9
  • P_i \neq P_j\ (i \neq j)
  • 输入中的所有值都是整数。

输入

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

N
P_1 P_2 \ldots P_N
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_N B_N C_N

输出

打印实现目标之前需要支付的最低总成本。


示例输入 1

3
3 1 2
9 3 5
8 6 4
9 4 6

示例输出 1

6

通过支付费用可以按照ID号从小到大的顺序重新排列人员 C_3=6 移动人员 3 到右端。

没有办法重新安排成本较低的人员,所以答案是 6.


示例输入 2

6
2 6 5 3 4 1
10 8 16
30 2 10
10 17 8
11 27 22
8 6 5
15 29 2

示例输出 2

15

以下操作顺序可最大限度地降低总成本:

  • 支付费用 B_1=8 移动人员 1 到左端;
  • 支付费用 C_5=5 移动人员 5 到右端;
  • 支付费用 C_6=2 移动人员 6 到右端。

示例输入 3

9
3 8 4 7 6 9 1 5 2
7976 3696 9706
768 8807 8521
1133 8683 7120
1189 3331 2259
900 7451 1159
6126 2639 7107
5540 8253 2891
8417 4220 9091
8732 1417 1540

示例输出 3

15865

示例输入 4

12
11 9 1 12 2 7 3 5 10 4 6 8
3960 3158 9029
6521 6597 7581
5688 2299 2123
4946 4298 9122
394 4350 9142
3098 7151 2039
8525 3758 6155
6970 3658 9353
9780 1778 3608
6065 5562 923
9701 5524 6482
9395 6016 705

示例输出 4

20637