21332번 - Magic Show 스페셜 저지다국어언어 제한함수 구현

Mårten the Magician is currently performing in a magnificent magic competition. The show consists of $N$ rounds. In each round, Mårten uses his magic to perform one of two tricks: either he makes some number $x$ rabbits appear, or he sabotages his opponents' tricks by making some number $y$ of their rabbits disappear. He can also choose to do neither.

For each rabbit Mårten makes appear or disappear, he must use 1 magick. In the beginning of the show, Mårten has $K$ magicks. When he has run out of magicks, he can no longer perform a trick.

The scoring of the competition is easy. In the $i$:th round, let \[ S_i = \begin{cases} x & \text{ if Mårten made $x$ rabbits appear } \\ -y & \text{ if Mårten made $y$ rabbits disappear } \\ 0 & \text{ if Mårten didn't perform a trick} \end{cases} \]

In round $i$, if $S_i$ is in the interval $[L[i], R[i]]$ where $L[i]$ and $R[i]$ are integers specific to the round, he gets $|S_i - \frac{L[i] + R[i]}{2}|$ points. If $S_i$ is outside this interval, Mårten gets $0$ points. Note that Mårten cannot perform his magic on fractional rabbits, thus $S_i$ will always be an integer.

Mårten's total score in the competition is the sum of scores among all the rounds. What is the maximum score Mårten can get if he performs optimally?

Consider a competition with $N = 4$ rounds, where Mårten has $K = 5$ magicks at the start of the show. The round intervals are $[3, 5]$ for the first round, $[-2, 2]$ for the second round, $[-2, 0]$ for the third round, and $[2, 6]$ for the last round.

The optimal play from Mårten is then to do nothing in the first round ($0$ points), remove two rabbits in the second ($|-2 - 0| = 2$ points), do nothing in the third round ($|0 - (-1)| = 1$ point), and create 2 rabbits in the last round ($|2 - 4| = 2$ points).

This totals $0 + 2 + 1 + 2 = 5$ points, which is the best possible score. Note that there are several optimal strategies in the example. In total, he used $0 + 2 + 0 + 2 = 4$ magicks, leaving an unused magick after the last round.

Given all the rounds of the competition, you are to determine the maximum score Mårten can get, and construct instructions for him.

You should implement the function magic_score(N, K, L, R).

• magic_score(N, K, L, R) - this function will be called exactly once by the judge.
  • N: the number of rounds in the competition.
  • K: the amount of magicks Mårten has in the beginning of the show.
  • L: an array with $N$ elements, containing the values L[i] as descriped in the task.
  • R: an array with $N$ elements, containing the values R[i] as descriped in the task.
  • $-1\,000\,000 \le L[i] \le R[i] \le 1\,000\,000$
  • $L[i] + R[i]$ is even
  • The function should return the maximum score Mårten can obtain.

Additionally, you should call the function trick(X) to tell Mårten what he should do in each round.

• trick(X) - this function should be called by your program once for every round. The $i$:th call should give the instruction to Mårten in the $i$:th round if Mårten wants to play optimally.
  • X: this parameter should give the value $S_i$ of each of Mårten's rounds. If Mårten should add rabbits, this value should be the number of rabbits Mårten should add. If he should remove rabbits, it should be the negative value of the number of rabbits he removes. If he should not do any trick in the round, the value should be $0$. 
  • The function has no return value.

A code skeleton containing the function to be implemented, together with a sample grader, can be found at attachments.zip.

The sample judge reads input in the following format:

• line $1$: N K
• line $2$: L[0] L[1] .. L[N - 1]
• line $3$: R[0] R[1] .. R[N - 1]

The sample judge writes output in the following format:

• line $1$: the return value of magic_score(N, K, L, R) on a line
• line $2$: $N$ integers, the values given from the calls to trick(X) in order.

• $N \le 1\,000$
• $K \le 1,000$