P3991 [BJOI2017] Jet Water War Kai

Got a pilot license for airplanes (?), so resupply is no longer a problem. XXXX year XX month XX day. Got a pilot license for jets (??), so I can fly even faster. XXXX year XX month XX day. Got a pilot license for attack aircraft (???), which does not exist. XXXX year XX month XX day. If you use lead plates for the sandwich structure, the fuselage will get heavier. XXXX year XX month XX day. Kou-chan’s special delivery was precisely dropped on the target. ------------------------------------- Another day of “nuke-peace.” Amane is doing maintenance on the jet and refueling it. This jet was specially made by a certain “mou ji” (某姬). Its engine has three operating states: 1. Original: a low-power, high-efficiency state used for high-altitude level flight or stealth flight. 2. Extended: a state specially modified to maximize energy utilization during a dive. 3. Enhanced: a state used after a diving attack to generate extreme torque and regain altitude. In one attack, the jet will go through the workflow “Original → Extended → Enhanced → Original.” Fuel utilization efficiency differs across states. Amane is now tuning the jet’s fuel loading sequence. Your task is to compute the maximum total energy the fuel can produce. Why you? Choose one: peace or “nuke-peace.”

The initial fuel sequence is empty. Each operation inserts $x _ i$ units of the same type of fuel at position $p _ i$ in the sequence. For this fuel, each unit can produce energy $a _ i, b _ i, c _ i$ in the three operating states, respectively. The position $p _ i$ means that, after insertion, there are $p _ i$ units of the original fuel in front of the first inserted unit. All $x _ i$ units are placed consecutively. Then the fuel that originally started at position $p _ i$ (if any) is shifted backward in order. For a fixed fuel sequence, its maximum total energy is defined as follows: split the sequence into four consecutive segments in the order “Original → Extended → Enhanced → Original” (each segment may be empty). The total energy is the sum, over all units, of the energy corresponding to the state of the segment they belong to. Take the maximum value over all such splits. For each insertion operation, output by how much the maximum total energy increases due to this operation. If this calculation is not intuitive, see the sample explanation.

The first line contains an integer $n$, the number of operations. Each of the next $n$ lines contains $5$ integers $p _ i, a _ i, b _ i, c _ i, x _ i$, separated by spaces, indicating that $x _ i$ units of the same fuel are inserted at position $p _ i$ in the sequence. For this fuel, each unit produces $a _ i, b _ i, c _ i$ energy in the Original, Extended, and Enhanced states, respectively.

Output $n$ lines. Each line contains a single integer, the increase in the maximum total energy after that operation.

After the first operation, the fuel sequence is “[1 1]”. The way to achieve maximum energy is “[En1 En1]”, totaling $46+46=92$. After the second operation, the fuel sequence is “[1 2 2 2 1]”. The way to achieve maximum energy is “[Or1 Or2 Or2 Or2 En1]”, totaling $25+32+32+32+46=167$, increased by $167-92=75$. After the third operation, the fuel sequence is “[1 2 2 3 3 3 3 2 1]”. The way to achieve maximum energy is “[Or1 Or2 Or2 Or3 Or3 Or3 Or3 Or2 En1]”, increased by $99\times 4=396$. After the fourth operation, the fuel sequence is “[1 2 4 4 4 4 4 2 3 3 3 3 2 1]”. The way to achieve maximum energy is “[Or1 Or2 Ex4 Ex4 Ex4 Ex4 Ex4 Or2 Or3 Or3 Or3 Or3 Or2 Or1]”. After the fifth operation, the fuel sequence is “[1 2 4 4 4 4 4 2 3 3 3 3 2 1 5 5 5 5 5 5]”. The way to achieve maximum energy is “[Or1 Or2 Ex4 Ex4 Ex4 Ex4 Ex4 Or2 Or3 Or3 Or3 Or3 Or2 Or1 Or5 Or5 Or5 Or5 Or5 Or5]”. For $100\%$ of the testdata, $1 \leq n \leq 10^5$, $1 \leq a_i, b_i, c_i \leq 10^4$, $1 \leq x_i \leq 10^9$. For $100\%$ of the testdata, it is guaranteed that at the time of insertion there are at least $p _ i$ units of fuel already in the sequence. The remaining $50\%$ of the testdata has graded difficulty. Translated by ChatGPT 5