F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Problem 2122. -- 工作评估

2122: 工作评估

Time Limit: 50 Sec  Memory Limit: 259 MB
Submit: 408  Solved: 214
[Submit][Status][Discuss]

Description

利用空闲时间,BX希望外出工作,工作开始之前,公司就会给BX一个评估值X0,之后每天BX的评估值都是根据上一
天的评估值和当天公司的运行状况得出,即Xi=Xi-1+Di,但是每天的评估值有一个上限,也就是说完整的评估公式
因该是Xi=min{Xi-1+Di,Li}。现在BX已经知道了该公司对自己的初始评估值X0、公司每天的运行状况Di、每天的评
估上限Li,他的空闲时间是从第A天到第B天,他希望找到一段时间i,j (A≤i≤j≤B),使得从第i天开始工作,到
第j天结束后的评估值最大。当然如果任意一段时间的工作得到评估值都<初始评估值X0,BX可以选择不工作,从而
得到最大的评估值。

Input

输入的第一行包含两个整数N、M,分别表示总共工作天数和询问数。
第二行N个数,表示Di。第三行N个数,表示Li。
以下M行,每行3个数A、B、X0,表示一次询问。

Output

M行,每行输出一个整数,表示评估的最大值

Sample Input

6 3
-6 5 3 2 -3 4
8 10 8 1 9 9
1 3 9
2 6 3
3 4 0

Sample Output

10
8
3
【数据规模】
对于100%数据,满足N,M<50001,|Di|<10001,0≤Li<1000000001

HINT

Source

[Submit][Status][Discuss]

HOME Back