喷式水战改 - 题目

题目背景

拿到了飞机的驾照(?)，这样补给就不愁了 XXXX年XX月XX日

拿到了喷气机(??)的驾照，这样就飞得更快了 XXXX年XX月XX日

拿到了攻击机(???)的驾照（不存在的） XXXX年XX月XX日

用铅版做夹层的话，机身可是会变重的呢 XXXX年XX月XX日

幸酱的特制快递，精确投递到了目标地点

又是核平的一天。

天音正在给喷气机做保养，并充填燃料。这种喷气机是某姬（?????）特别制作的，发动机拥有三种工作状态：

通常型（Original）：在高空平飞或隐蔽飞行时进行的低功耗高效率工作状态
后期型（Extended）：为在俯冲时最大化能量利用率而特别改造过的工作状态
增强型（Enhanced）：在俯冲攻击结束后为产生极限扭力抬高高度的工作状态

在一次攻击中，喷气机将会经历 "通常 → 后期 → 增强 → 通常" 的工作流程。

不同工作状态中，燃料的利用效率是不同的。现在天音正在调整喷气机燃料装填序列，你需要做的就是：

求出燃料能产生的最大总能量。

为什么是你？和平还是核平，选一个吧。

题目描述

初始燃料序列为空。每次操作会向序列中的第 $p_i$ 个位置添加 $x_i$ 单位的同种燃料。

该燃料每单位在三种工作状态下能产生的能量分别为 $a_i,\ b_i,\ c_i$。

添加的位置 $p_i$ 是指，在添加后，加入的第一个单位燃料前面有 $p_i$ 个单位的原燃料。
全部的 $x_i$ 单位燃料依次放置，然后原来在 $p_i$ 位置的燃料（如果有的话）依次向后排列。

对于一个确定的燃料序列，其能产生的最大总能量为：

将序列依次分成 "通常 → 后期 → 增强 → 通常" 四段（每段可以为空），每一段在对应工作状态下产生的能量之和的最大值。

对于每次添加操作，你需要给出该次操作使得最大总能量增加了多少。

如果对这种计算方式没有直观的感受，可以查看样例说明。

输入格式

第一行一个整数 $n$，表示操作个数。

接下来 $n$ 行，每行包含 5 个整数 $p_i,\ a_i,\ b_i,\ c_i,\ x_i$，空格分隔，含义如下：

$p_i$：插入的位置
$a_i,\ b_i,\ c_i$：单位燃料在通常、后期、增强三种状态下产生的能量
$x_i$：添加的燃料数量

输出格式

输出 $n$ 行，每行一个整数，表示该次操作后燃料序列所能产生的最大总能量增加了多少。

样例数据

样例输入

5
0 25 37 46 2
1 32 14 16 3
3 99 77 88 4
2 43 68 57 5
14 72 36 18 6

样例输出

样例解释

第一次操作后，燃料序列为 [1 1] 最大能量发生方式为 [En1 En1]，共 $46 + 46 = 92$

第二次操作后，燃料序列为 [1 2 2 2 1] 最大能量发生方式为 [Or1 Or2 Or2 Or2 En1]，共 $25 + 32 + 32 + 32 + 46 = 167$，增加了 $167 - 92 = 75$

第三次操作后，燃料序列为 [1 2 2 3 3 3 3 2 1] 最大能量发生方式为 [Or1 Or2 Or2 Or3 Or3 Or3 Or3 Or2 En1]，增加了 $99 \times 4 = 396$

第四次操作后，燃料序列为 [1 2 4 4 4 4 4 2 3 3 3 2 1] 最大能量发生方式为 [Or1 Or2 Ex4 Ex4 Ex4 Ex4 Ex4 Or2 Or3 Or3 Or3 Or3 Or2 Or1]

第五次操作后，燃料序列为 [1 2 4 4 4 4 4 2 3 3 3 2 1 5 5 5 5 5 5] 最大能量发生方式为 [Or1 Or2 Ex4 Ex4 Ex4 Ex4 Ex4 Or2 Or3 Or3 Or3 Or3 Or2 Or1 Or5 Or5 Or5 Or5 Or5 Or5]

子任务

对于 $20\%$ 的数据，$n \leq 1\,000$。

对于 $50\%$ 的数据，$n \leq 10^4$。

对于 $100%$ 的数据：$1 \le n \le 10^5$，$1 \le a_i,\ b_i,\ c_i \le 10^4$，$1 \le x_i \le 10^9$。后 $50\%$ 的数据存在一定的梯度。

保证插入时序列中至少已有 $p_i$ 单位的燃料

QOJ.ac

QOJ

# 10365. 喷式水战改