Excitation of Atoms
Contest: 2020 ICPC, COMPFEST 12, Indonesia Multi-Provincial Contest (Unrated, Online Mirror, ICPC Rules, Teams Preferred)
Difficulty rating: 2200
Tags: greedy, implementation

Mr. Chanek is currently participating in a science fair that is popular in town. He finds an exciting puzzle in the fair and wants to solve it.

There are $$$N$$$ atoms numbered from $$$1$$$ to $$$N$$$. These atoms are especially quirky. Initially, each atom is in normal state. Each atom can be in an excited. Exciting atom $$$i$$$ requires $$$D_i$$$ energy. When atom $$$i$$$ is excited, it will give $$$A_i$$$ energy. You can excite any number of atoms (including zero).

These atoms also form a peculiar one-way bond. For each $$$i$$$, $$$(1 \le i < N)$$$, if atom $$$i$$$ is excited, atom $$$E_i$$$ will also be excited at no cost. Initially, $$$E_i$$$ = $$$i+1$$$. Note that atom $$$N$$$ cannot form a bond to any atom.

Mr. Chanek must change exactly $$$K$$$ bonds. Exactly $$$K$$$ times, Mr. Chanek chooses an atom $$$i$$$, $$$(1 \le i < N)$$$ and changes $$$E_i$$$ to a different value other than $$$i$$$ and the current $$$E_i$$$. Note that an atom's bond can remain unchanged or changed more than once. Help Mr. Chanek determine the maximum energy that he can achieve!

note: You must first change exactly $$$K$$$ bonds before you can start exciting atoms.

Input format:
The first line contains two integers $$$N$$$ $$$K$$$ $$$(4 \le N \le 10^5, 0 \le K < N)$$$, the number of atoms, and the number of bonds that must be changed.

The second line contains $$$N$$$ integers $$$A_i$$$ $$$(1 \le A_i \le 10^6)$$$, which denotes the energy given by atom $$$i$$$ when on excited state.

The third line contains $$$N$$$ integers $$$D_i$$$ $$$(1 \le D_i \le 10^6)$$$, which denotes the energy needed to excite atom $$$i$$$.

Output format:
A line with an integer that denotes the maximum number of energy that Mr. Chanek can get.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
An optimal solution to change $$$E_5$$$ to 1 and then excite atom 5 with energy 1. It will cause atoms 1, 2, 3, 4, 5 be excited. The total energy gained by Mr. Chanek is (5 + 6 + 7 + 8 + 10) - 1 = 35.

Another possible way is to change $$$E_3$$$ to 1 and then exciting atom 3 (which will excite atom 1, 2, 3) and exciting atom 4 (which will excite atom 4, 5, 6). The total energy gained by Mr. Chanek is (5 + 6 + 7 + 8 + 10 + 2) - (6 + 7) = 25 which is not optimal.

Example input:
6 1
5 6 7 8 10 2
3 5 6 7 1 10

Example output:
35

Editorial:
Notice that for $$$K = 2$$$, we can always make an excitation route starting from any atom in $$$i$$$ in $$$1 \le i < N$$$ that excites all atoms. So, for $$$K > 2$$$, we can always make the routes by toggling bonds. So, there are three cases:
If $$$K = 0$$$, it is optimal to excite only one atom. We try to excite atom $$$i$$$ for every $$$i$$$ and calculate the gained energy using prefix sum.
If $$$K \ge 2$$$, we can either excite one atom $$$i$$$ in $$$1 \le i < N $$$, which will excite all atoms or excite only the last atom (which can be optimal if it has the lowest $$$D$$$).
$$$K = 1$$$ is a tricky one. there are 5 cases to consider:
1. change $$$E_{N-1}$$$ to $$$1$$$. Then excite the atom with the $$$D_i$$$ in $$$1 \le i < N$$$. Also, excite atom $$$N$$$ if the energy gained is positive.
2. change $$$E_i$$$ to $$$1$$$ and then excite atom $$$i$$$ and $$$i+1$$$ for $$$(1 < i < N)$$$. It is optimal to excite $$$i+1$$$ because if not, it will be worse than case 1.
3. Change $$$E_1$$$ to $$$3$$$ and then excite $$$1$$$ and $$$2$$$.
4. Change $$$E_1$$$ to $$$N$$$ and then excite atom $$$i$$$, for $$$(1 < i \le N)$$$
5. Change $$$E_i$$$ to $$$i+2$$$ and then excite atom $$$1$$$, for $$$(1 < i < N)$$$. Note that this is only optimal if we excite atom $$$1$$$, else it is worse than case $$$4$$$
Handling all these cases will get you accepted
Time complexity: $$$O(N)$$$