IOICamp 2024 題目公開！ 連結
程式解題社網站 程式解題社網站上線了！
停機公告 今（2025/01/15）15:00～18:00 本站將進行系統維護，期間將無法評分提交的程式碼。
48 . 代打
TopCoder
Tags
Description
小 A 和小 B 最近迷上了一個名為方塊工廠（Cube Factory, CF）的遊戲，這遊戲主要藉由建造方塊工廠來生產出戰鬥力極強的方塊們，並用生產出來的方塊跟別人比賽。遊戲每個禮拜都會舉辦一場比賽，比賽的表現越出色，就越能夠提升自己的分數，然而表現不如預期的話分數就會下降。
更詳細來說，每場比賽遊戲會藉由玩家表現來幫每位玩家決定出一個「表現值」，而假設在比賽開始前，某位玩家的分數為 $a$，而他參加了一場表現值為 $b$ 的比賽後分數變成 $a'$，則 $a'$ 會滿足：
$$
\begin{cases}a' = a + \lfloor\sqrt{b - a}\rfloor & \text{if} \ a \leq b \\ a' = a - \lfloor\sqrt{a - b}\rfloor & \text{if} \ a > b \end{cases}
$$
其中 $\lfloor x \rfloor$ 為下高斯符號，代表小於或等於 $x$ 中最大的整數。而 $\sqrt{x}$ 為 $x$ 的根號。
身為 CF 的上癮玩家，他們已經預測出了兩個人接下來 $N$ 個禮拜的比賽的表現值為何，然而小 A 對自己的表現不太滿意，但他又希望能繼續維持「比賽全勤」的成就，因此他希望小 B 可以幫他代打幾場，好讓這 $N$ 場比賽比完後他的分數越高越好。然而為了避免被其他玩家發現而被檢舉，小 B 最多只能幫小 A 代打 $K$ 場。你能幫幫小 A 計算在最優的策略下，$N$ 場比賽比完後他的分數最多會是多少呢？
Input Format
輸入第一行有三個整數 $N, K, X$，分別代表比賽的場數、小 B 最多可以代打的場數以及小 A 一開始的分數。
輸入第二行有 $N$ 個整數 $a_1, a_2, \ldots, a_N$，其中 $a_i$ 為小 A 在第 $i$ 場比賽的表現值。
輸入第三行有 $N$ 個整數 $b_1, b_2, \ldots, b_N$，其中 $b_i$ 為小 B 在第 $i$ 場比賽的表現值。
- $1 \leq N \leq 10^ 5$
- $0 \leq K \leq 20$
- $K \leq N$
- $0 \leq X, a_i, b_i \leq 10^ {18}$
Output Format
請輸出一行，該行有一個整數，代表在至多找小 B 代打 $K$ 場的情況下，小 A 比完 $N$ 場比賽後他的分數最多是多少。
Sample Input 1
8 0 3 6 8
9 7 4 3 1
Sample Output 1
Sample Input 2
8 6 4 1 9 7 5 3 2
1 2 3 4 5 6 7 8 9
Sample Output 2
Sample Input 3
78 19 26 3 87 68 23 68 31 60 45 11 24 51 63 82 58
80 61 38 72 89 85 83 84 55 92 69 50 44 73 88 88 97
Sample Output 3
Hints
在第一筆範例測試資料中：
- 若小 A 選擇在第 $1$ 場找小 B 代打，則分數變化為：$5 \to 7 \to 5 \to 4 \to 5 \to 6$
- 若小 A 選擇在第 $2$ 場找小 B 代打，則分數變化為：$5 \to 6 \to 7 \to 5 \to 6 \to 7$
- 若小 A 選擇在第 $3$ 場找小 B 代打，則分數變化為：$5 \to 6 \to 4 \to 4 \to 5 \to 6$
- 若小 A 選擇在第 $4$ 場找小 B 代打，則分數變化為：$5 \to 6 \to 4 \to 3 \to 3 \to 5$
- 若小 A 選擇在第 $5$ 場找小 B 代打，則分數變化為：$5 \to 6 \to 4 \to 3 \to 4 \to 3$
因此答案為 $7$。
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 範例測資 | 0 |
| 2 | 1, 3~12 | $K = 0$ | 20 |
| 3 | 3~57 | 無額外限制 | 80 |