← 返回题目列表

AtCoder · oupc2023_day1_n

N. 长凳

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

配点 : 100 点

問題文

旁边有一个长凳。 1 有一个。 板凳上 已分配最大 1 它们的编号最大为 L 的整数 L 垫子排成一排,每个垫子 i (1\leq i\leq L-1) 关于坐垫 i 和坐垫 i+1 彼此相邻。

这张长凳上有一群人。N 你们将被分成几组并按顺序就座。 第 j 组是 A_j 由坐在长凳上的人组成 A_j 坐垫(更准确地说,一个 p 关于坐垫 p,p+1,\dots,p+A_j-1)到 1 让每个人坐下。 彼此相邻 如果没有 A_j 坐垫全部无人占用,则该小组将 失敗 坐下来 失敗 当一组决定坐在替补席上时,其余组就会放弃坐在替补席上。 在第

1 组来坐替补席之前,KowerKoint可以花钱增加或减少该组的人数。 具体来说,执行以下操作任意次数(0 次)。

  • B_j 日元付款,j 群组人数 1 减少人数( 第j 组的人数为 2 只有多人时才能完成)
  • C_j 日元付款,j 群组人数 1 增加人数

但是,手术期间或手术后您所拥有的资金不得变为负值。 还,B_j 可以为负,-x 支付日元是什么意思? x 表示您将收到日元。

无论每组选择坐在哪里,最终总分是 y 最大的座位区,可容纳多人。 考虑 y 。 KowerKoint 你是这样的 我想通过操作最大化 y 。 整数 Q 和非负整数序列 给出了 M_1,M_2,\dots,M_Q ,所以每个 关于 k (1\leq k\leq Q) ,您在手术前拥有的金额是 M_k 当它是一个圆时 请回答 y 的最大值。

制約

  • 1 \leq N \leq L \leq 3{,}000
  • 1 \leq A_j \leq L
  • -10^{9} \leq B_j \leq 10^{9}
  • 0 \leq C_j \leq 10^{9}
  • 1 \leq B_j+C_j
  • 1 \leq Q \leq 200{,}000
  • 0 \leq M_k \leq 10^{15}
  • 输入全部为整数

小課題

  1. (1 点) B_j=1,C_j=1,Q=1,M_k=0
  2. (99 点)无附加约束 请输出

入力

输入是按以下格式从标准输入给出的。 请按降序输出

N L
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_N B_N C_N
Q
M_1
M_2
\vdots
M_Q

出力

Q 行。 k 行显示您在操作之前拥有的金额。 M_k 当是一个圆圈时,请使用KowerKoint输出无论怎么坐都能坐的最大人数。 在第


入力例 1

3 7
2 5 2
4 1 2
2 3 0
4
0
1
5
10

出力例 1

2
5
6
7
  • 1 个查询中,KowerKoint 是 0 我有日元。如果不操作1 第组 2 只有人可以坐。 您可以随意增加第3 组的人数,但增加人数并不一定会增加可以坐的人数。
  • 2 个查询中,KowerKoint 是 1 我有日元。1 支付日元 2 群组人数 1 如果减少人数,2 最多组 2+3=5 总有空间可以让人坐,这是最大的。
  • 3 个查询中,KowerKoint 是 5 我有日元。1 支付日元 2 群组人数 1 减少人数,3 支付日元 3 群组人数 1 如果减少人数,2+3+1=6 大家绝对可以坐,这是最多的。
  • 4 个查询中,KowerKoint 是 10 我有日元。2\times5=10 支付日元 1 群组人数 5 如果增加人数,1 第组 7 总有空间可以让人坐,这是最大的。

该测试用例不满足子任务 1 的约束。


入力例 2

3 8
2 1 1
3 1 1
2 1 1
1
0

出力例 2

5

该测试用例满足子任务 1 的约束。


入力例 3

7 20
3 1 4
2 -2 7
4 1 1
1 -3 8
9 2 4
6 3 1
4 -2 5
6
8
0
3
10
17
2

出力例 3

13
12
13
14
15
12

该测试用例不满足子任务 1 的条件。