← 返回题目列表

AtCoder · joi2013yo_d

D. 炎热的日子

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

配点: 100 点

問題

虽然日本正值冬季,但位于南半球的澳大利亚却持续炎热。您是居住在澳大利亚的 IOI 吗? D 我决定根据当天的天气预报来计划穿什么衣服。i 日目 (1 \leqq i \leqq D) 中的最高温度为 预计为 T_i 度。

IOI你 N 我有不同种类的衣服,其中包括 它们的编号最大为 1 到 N 。衣服 j (1 \leqq j \leqq N) 的最高温度为 A_j 度以上 B_j 适合气温低于30度的日子穿着。另外,每件衣服都有一个固定的整数,称为“gaiety”,并且 j 的华丽 C_j 。

D IOI会根据天气预报每天选择最高气温时适合穿哪些衣服。 1 选择一件作为要穿的衣服。您可以一遍又一遍地选择相同的衣服。D 拥有一天不选的衣服也没关系。

想要尽可能避免连续穿着类似的衣服,IOI决定让连续几天穿着的衣服的华丽度差异的绝对值之和尽可能大。也就是说,i 当天的衣服 如果选择 x_i ,则该值 我想最大化 |C_{x_1} - C_{x_2}| + |C_{x_2} - C_{x_3}| + \cdots + |C_{x_{D-1}} - C_{x_D}| 。编写一个程序来找到这个最大值。 由


入力

输入是 有时您需要的只是 1 + D + N 行组成。 在

1 行中,2 整数 D, N (2 \leqq D \leqq 200,1 \leqq N \leqq 200)以空格作为分隔符。D 是计划衣服的天数,N 代表IOI拥有的衣服种类数量。

继续 D 行 i 行目 (1 \leqq i \leqq D)有1 整数 T_i (0 \leqq T_i \leqq 60)被写入。这是i 当日最高气温为 T_i 预计为 2 度。

继续 N 行 j 行目 (1 \leqq j \leqq N)有3 整数 A_j, B_j, C_j (0 \leqq A_j \leqq B_j \leqq 60,0 \leqq C_j \leqq 100)被写入。这些是衣服。 j 的最高温度为 A_j 度以上 B_j 适合低于℃的日子穿着,不浮夸。 C_j 。

天气预报最高气温时适合穿的衣服有:D 一天中的任何一天 1 保证至少有一个。

出力

连续天穿着的衣服的花哨度差值的绝对值之和,即值 |C_{x_1} - C_{x_2}| + |C_{x_2} - C_{x_3}| + \cdots + |C_{x_{D - 1}} - C_{x_D}| 的最大值 输出为 1 行。 在


入力例 1

3 4
31
27
35
20 25 30
23 29 90
21 35 60
28 33 40

出力例 1

80

入出力例 1 中,1 当天的候选服装是服装。 3 和衣服 4 和 仅2 当天的候选服装是服装。 2 和衣服 3 和 仅3 当天的候选服装是服装。 3 。1 当天的衣服 如果选择 4 , 选择2 当天的衣服 如果选择 2 , 选择3 当天的衣服 如果选择 3 。也就是说,x_1 = 4,x_2 = 2,x_3 = 3 。这时,1 日和 2 当天衣服的花哨度差异的绝对值为 |40 - 90| = 50 和 仅2 日和 3 当天衣服的花哨度差异的绝对值为 |90 - 60| = 30 。总计为 80 ,这是最大值。


入力例 2

5 2
26
28
32
29
34
30 35 0
25 30 100

出力例 2

300

入出力例 2 中,1 当天服装 必须选择 2 , 选择2 当天服装 必须选择 2 , 选择3 当天服装 必须选择 1 , 选择4 当天服装 必须选择 2 , 选择5 当天服装 必须选择 1 。此时,期望值为 |100 - 100| + |100 - 0| + |0 - 100| + |100 - 0| = 300 变为。