AT_arc137_e.[ARC137E] Bakery

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

すぬけ君是一家面包店的老板。他正在为接下来的 $N$ 天制定营业计划。我们将这些天分别称为第 $1,2,\cdots,N$ 天。

目前，这家店还没有任何面包师。现在有 $M$ 位面包师候选人，编号为 $1$ 到 $M$ 。

雇佣第 $i$ 位面包师需要支付 $C_i$ 日元。如果雇佣了第 $i$ 位面包师，他将在第 $L_i,L_i+1,\cdots,R_i$ 天工作，并且每天制作 $1$ 个面包。

对于每一天 $j$ （ $1\leq j\leq N$ ），第 $j$ 天最多能卖出的面包数量为 $A_j$ 。如果第 $j$ 天制作了 $x_j$ 个面包，那么当天能卖出的面包数量为 $\min(x_j, A_j)$ 。

每卖出一个面包可以获得 $D$ 日元的利润。

すぬけ君希望通过合理选择要雇佣的面包师集合，使得最终利润
$=$ (卖出的面包总数) $\times D-$ (雇佣面包师的总花费)
最大。请你求出这个最大值。

输入以如下格式从标准输入读入。

$N$ $M$ $D$
$A_1$ $A_2$ $\cdots$ $A_N$
$L_1$ $R_1$ $C_1$
$L_2$ $R_2$ $C_2$
$\vdots$
$L_M$ $R_M$ $C_M$

请输出答案。

输入#1

7 4 3
1 1 1 1 1 1 1
1 2 3
2 4 5
4 6 3
6 7 1

输出#1

输入#3

10 10 42
6 5 1 5 2 4 2 7 10 9
3 4 4
3 7 136
9 9 14
2 7 152
3 3 33
2 4 100
3 3 38
1 10 28
3 5 66
8 8 15

输出#3

雇佣第 $1,3,4$ 位面包师即可。此时，雇佣面包师的总花费为 $7$ 。第 $1,2,\cdots,N$ 天分别制作的面包数量为 $1,1,0,1,1,2,1$ 。卖出的面包总数为 $6$ ，最终利润为 $6\times 3-7=11$ 。

一个面包师都不雇佣是最优的选择。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?