Excitation of Atoms SOLUTION
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 Di energy. When atom i is excited, it will give Ai energy. You can excite any number of atoms (including zero).
These atoms also form a peculiar one-way bond. For each i, (1≤i<N), if atom i is excited, atom Ei will also be excited at no cost. Initially, Ei = 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≤i<N) and changes Ei to a different value other than i and the current Ei. 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.
The first line contains two integers N K (4≤N≤105,0≤K<N), the number of atoms, and the number of bonds that must be changed.
The second line contains N integers Ai (1≤Ai≤106), which denotes the energy given by atom i when on excited state.
The third line contains N integers Di (1≤Di≤106), which denotes the energy needed to excite atom i.
A line with an integer that denotes the maximum number of energy that Mr. Chanek can get.
5 6 7 8 10 2
3 5 6 7 1 10
An optimal solution to change E5 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 E3 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.