8340: 洛谷P9228 - 原神
[Creator : ]
Description
原神中有一个魔法师，她可以打出 $ n $ 次火元素攻击魔法和 $ m $ 次冰元素攻击魔法，每次攻击的伤害分别为 $ a_1,a_2,\cdots, a_n $ 和 $ b_1,b_2,\cdots, b_m $。
元素攻击之间存在如下反应规则：
- 每次元素攻击可以给**没有元素附着**的怪物附着相应的元素，初始时怪物没有元素附着；
- 如果用火元素攻击打到冰元素附着的怪物身上，那么本次伤害将 $ \times 2 $，并清空元素附着；
- 如果用冰元素攻击打到火元素附着的怪物身上，那么本次伤害将 $ +k $，并清空元素附着。
现在魔法师可以任意安排攻击顺序，也就是说，每次攻击过后，魔法师可以从自己没有使用过的魔法中任意挑选一种使用。她希望最大化总伤害，请问最大总伤害是多少。
元素攻击之间存在如下反应规则：
- 每次元素攻击可以给**没有元素附着**的怪物附着相应的元素，初始时怪物没有元素附着；
- 如果用火元素攻击打到冰元素附着的怪物身上，那么本次伤害将 $ \times 2 $，并清空元素附着；
- 如果用冰元素攻击打到火元素附着的怪物身上，那么本次伤害将 $ +k $，并清空元素附着。
现在魔法师可以任意安排攻击顺序，也就是说，每次攻击过后，魔法师可以从自己没有使用过的魔法中任意挑选一种使用。她希望最大化总伤害，请问最大总伤害是多少。
Input
第一行三个整数 $ n,m,k $。
第二行 $ n $ 个整数 $ a_1,a_2,\cdots, a_n $。
第三行 $ m $ 个整数 $ b_1,b_2,\cdots, b_m $。
第二行 $ n $ 个整数 $ a_1,a_2,\cdots, a_n $。
第三行 $ m $ 个整数 $ b_1,b_2,\cdots, b_m $。
Output
一行一个整数，表示答案。
|
测试点编号 |
$n,m \leq$ |
特殊性质 |
|
$1 \sim 5$ |
$10$ |
|
|
$6 \sim 10$ |
$1000$ |
|
|
$11 \sim 12$ |
$10 ^6 $ |
$k=0$ |
|
$13 \sim 14$ |
$10 ^6 $ |
$k>\max(\max_{i=1}^n\{a_i\},\max_{i=1}^m\{b_i\})$ |
|
$15 \sim 16$ |
$10 ^6 $ |
$n=m$ |
|
$17 \sim 25$ |
$10 ^6 $ |
|
Constraints
对于 $100\%$ 的数据，$1 \leq n,m \leq 10^6 $，$ 0 \leq a_i,b_i,k \leq 10^9 $。
Sample 1 Input
6 7 3
1 1 4 5 1 4
1 9 1 9 8 1 0
Sample 1 Output
67
攻击采用 $a_1\rightarrow b_4\rightarrow a_2\rightarrow b_3\rightarrow a_5\rightarrow b_5\rightarrow b_7 \rightarrow b_1\rightarrow a_3 \rightarrow b_2\rightarrow a_4\rightarrow b_3 \rightarrow a_6 $，每次的实际伤害为 $1,12,1,4,1,11,0,1,8,9,10,1,8$，总伤害为 $ 67 $。
Sample 2 Input
5 3 5
1 4 2 8 5
7 1 4
Sample 2 Output
50
攻击采用 $a_5\rightarrow b_1\rightarrow b_2\rightarrow a_4\rightarrow a_3\rightarrow b_3\rightarrow a_2\rightarrow a_1$，每次的实际伤害为 $5,12,1,16,2,9,4,1$，总伤害为 $50 $。
Sample 3 Input
1 1 0
2
3
Sample 3 Output
7
HINT
相同题目：洛谷P9228。