配点: 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 变为。