#P9789. 图的直径

    ID: 6412 传统题 1000ms 256MiB 尝试: 21 已通过: 8 难度: 8 上传者: 标签>CF2500提高+/省选-二分答案线性 DP支配关系一维前缀和同向双指针复制数组处理环

图的直径

题目描述

有两条无向链。每条链各有 n+1n+1 个点,编号为 0,1,…,n0,1,\ldots,n。第一条链中,编号为 ii 和 i+1i+1 的点之间的边长为 aia_i。第二条链中,对应边长为 bib_i。

从 0,1,…,n0,1,\ldots,n 中选择 kk 个不同的编号。对每个选中的编号 ii,在两条链的 ii 号点之间加入一条长度为 00 的无向边。

图的直径是任意两点之间最短路长度的最大值。求添加零边之后可能达到的最小直径。

输入格式

第一行两个整数 n,kn,k。第二行 nn 个整数 a0,…,an−1a_0,\ldots,a_{n-1}。第三行 nn 个整数 b0,…,bn−1b_0,\ldots,b_{n-1}。

输出格式

输出一行一个整数,表示最小直径。

样例

5 4
2 1 1 1 2
1 9 1 9 1
6

原赛样例 2–4 见下发文件。

数据范围

1≤n≤2001\le n\le200,1≤k≤n+11\le k\le n+1,1≤ai,bi≤501\le a_i,b_i\le50。

原赛子任务 特殊限制 原赛分值
1 n≤10n\le10 30
2 k=1k=1 20
3 k=2k=2
4 无 30

原 PDF 题面