48 . 代打

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

94.4% (17/18)

Submission's AC Ratio

52.5% (21/40)

Tags

ioicamp ioicamp-2024

Description

小 A 和小 B 最近迷上了一個名為方塊工廠（Cube Factory, CF）的遊戲，這遊戲主要藉由建造方塊工廠來生產出戰鬥力極強的方塊們，並用生產出來的方塊跟別人比賽。遊戲每個禮拜都會舉辦一場比賽，比賽的表現越出色，就越能夠提升自己的分數，然而表現不如預期的話分數就會下降。

更詳細來說，每場比賽遊戲會藉由玩家表現來幫每位玩家決定出一個「表現值」，而假設在比賽開始前，某位玩家的分數為 a，而他參加了一場表現值為 b 的比賽後分數變成 a′，則 a′ 會滿足：

{a′=a+⌊b−a⌋if a≤ba′=a−⌊a−b⌋if a>b

其中 ⌊x⌋ 為下高斯符號，代表小於或等於 x 中最大的整數。而 x 為 x 的根號。

身為 CF 的上癮玩家，他們已經預測出了兩個人接下來 N 個禮拜的比賽的表現值為何，然而小 A 對自己的表現不太滿意，但他又希望能繼續維持「比賽全勤」的成就，因此他希望小 B 可以幫他代打幾場，好讓這 N 場比賽比完後他的分數越高越好。然而為了避免被其他玩家發現而被檢舉，小 B 最多只能幫小 A 代打 K 場。你能幫幫小 A 計算在最優的策略下，N 場比賽比完後他的分數最多會是多少呢？

Input Format

輸入第一行有三個整數 N,K,X，分別代表比賽的場數、小 B 最多可以代打的場數以及小 A 一開始的分數。

輸入第二行有 N 個整數 a1,a2,…,aN，其中 ai 為小 A 在第 i 場比賽的表現值。

輸入第三行有 N 個整數 b1,b2,…,bN，其中 bi 為小 B 在第 i 場比賽的表現值。

  • 1≤N≤105
  • 0≤K≤20
  • K≤N
  • 0≤X,ai,bi≤1018

Output Format

請輸出一行，該行有一個整數，代表在至多找小 B 代打 K 場的情況下，小 A 比完 N 場比賽後他的分數最多是多少。

Sample Input 1

5 1 5
8 0 3 6 8
9 7 4 3 1

Sample Output 1

7

Sample Input 2

9 0 314159265358979323
8 6 4 1 9 7 5 3 2
1 2 3 4 5 6 7 8 9

Sample Output 2

314159260314487250

Sample Input 3

17 8 47
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

74

Hints

在第一筆範例測試資料中：

  • 若小 A 選擇在第 1 場找小 B 代打，則分數變化為：5→7→5→4→5→6
  • 若小 A 選擇在第 2 場找小 B 代打，則分數變化為：5→6→7→5→6→7
  • 若小 A 選擇在第 3 場找小 B 代打，則分數變化為：5→6→4→4→5→6
  • 若小 A 選擇在第 4 場找小 B 代打，則分數變化為：5→6→4→3→3→5
  • 若小 A 選擇在第 5 場找小 B 代打，則分數變化為：5→6→4→3→4→3

因此答案為 7。

Problem Source

IOICamp 2024 Day6 pA

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 1, 3~12 K=0 20
3 0~57 無額外限制 80

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 3
1 1000 524288 65536 1 2 3
2 1000 524288 65536 1 3
3 1000 524288 65536 2 3
4 1000 524288 65536 2 3
5 1000 524288 65536 2 3
6 1000 524288 65536 2 3
7 1000 524288 65536 2 3
8 1000 524288 65536 2 3
9 1000 524288 65536 2 3
10 1000 524288 65536 2 3
11 1000 524288 65536 2 3
12 1000 524288 65536 2 3
13 1000 524288 65536 3
14 1000 524288 65536 3
15 1000 524288 65536 3
16 1000 524288 65536 3
17 1000 524288 65536 3
18 1000 524288 65536 3
19 1000 524288 65536 3
20 1000 524288 65536 3
21 1000 524288 65536 3
22 1000 524288 65536 3
23 1000 524288 65536 3
24 1000 524288 65536 3
25 1000 524288 65536 3
26 1000 524288 65536 3
27 1000 524288 65536 3
28 1000 524288 65536 3
29 1000 524288 65536 3
30 1000 524288 65536 3
31 1000 524288 65536 3
32 1000 524288 65536 3
33 1000 524288 65536 3
34 1000 524288 65536 3
35 1000 524288 65536 3
36 1000 524288 65536 3
37 1000 524288 65536 3
38 1000 524288 65536 3
39 1000 524288 65536 3
40 1000 524288 65536 3
41 1000 524288 65536 3
42 1000 524288 65536 3
43 1000 524288 65536 3
44 1000 524288 65536 3
45 1000 524288 65536 3
46 1000 524288 65536 3
47 1000 524288 65536 3
48 1000 524288 65536 3
49 1000 524288 65536 3
50 1000 524288 65536 3
51 1000 524288 65536 3
52 1000 524288 65536 3
53 1000 524288 65536 3
54 1000 524288 65536 3
55 1000 524288 65536 3
56 1000 524288 65536 3
57 1000 524288 65536 3
Submit
Back to Top