#C. 李代桃僵

    传统题 文件IO:li 1000ms 256MiB

李代桃僵

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

势必有损,损阴以益阳。

题目描述

33DAI 最近喜欢玩《骑马与砍杀 2》,他正领导着一支 nn 人的小队(保证 nn 是偶数),小队成员编号 1n1\sim n。他们中编号为 ii 的成员(1in21\le i\le \frac{n}{2})与编号为 i+n2i+\frac{n}{2} 的成员互为朋友关系。

为了掩护主力撤退,他决定选择其中 kk 名成员留下拖住敌人。显然选择的人不同,能拖住敌人的时间不一样。33DAI 提前了解过:

  • 编号为 ii 的成员如果朋友没有被留下,就有把敌人拖住 aia_i 秒的能力,
  • 否则如果他的朋友和他一起被留下了,就只能把敌人拖住 bib_i 秒的能力
  • 保证 biaib_i\le a_i
  • 最终拖住敌人的时间为每个被留下成员拖住敌人的能力之和。

请你算算怎么选择能把敌人拖住最久,输出最久的时间。

输入格式

第一行两个整数 n,kn,k

第二行为 nn 个整数 a1ana_1\sim a_n

第三行为 nn 个整数 b1bnb_1\sim b_n

输出格式

输出一个整数,即最久的时间。

4 3
10 11 11 12
9  7  8  6
29

留下 1,3,41,3,4,此时 1,31,3 互为朋友,能拖住 9+8=179+8=17 的时间,44 的朋友 22 没有被留下,能拖住 1212 的时间,一共拖住 2929 的时间。

10 7
89 94 96 50 70 27 75 87 98 24
53 81 3 27 5 12 39 19 97 13
499

数据规模与约定

对于 100%100\% 的数据,1k<n50001 \le k\lt n \le 50001biai50001\le b_i\le a_i\le 5000,保证 nn 是偶数。

  • 子任务 1(10 分):保证 k=2k=2
  • 子任务 2(20 分):保证 ai=bia_i=b_i
  • 子任务 3(30 分):保证 n=20n=20
  • 子任务 4(40 分):没有特殊限制。

挖土机 CSP-J 模拟赛 ~ 第九场

未参加
状态
已结束
规则
OI
题目
4
开始于
2024-10-1 4:00
结束于
2024-10-3 4:00
持续时间
3.5 小时
主持人
参赛人数
81