#2201. T3
T3
T3
题目描述
标题: T3 - Problem - QOJ.ac
#8370. T3
The problem was used in the following contests:
Alice 和 Bob 在玩游戏。
有一个 n×m 大小的棋盘,棋盘的第 x 行第 y 列记为 (x,y)。
开始时棋盘上有一个车位于 (1,1)。Alice 和 Bob 轮流操作,Alice 先操作。对于每次操作,玩家都有两种选择:
- 将车移动至同行或同列的某个格子上,注意不能移动到车本来所在的格子。换句话说,若车当前位于 (x,y),则它可被移动至 (c,y) (1≤c≤n,c≠x) 或 (x,d) (1≤d≤m,d≠y)。
- 结束游戏。
Alice 和 Bob 发现这个游戏可能永远不会结束,于是他们规定在任意时刻,每个格子被车移动到的次数要严格小于 109。注意,开始时格子 (1,1) 算作被移动到一次。
只是单纯地移动棋子非常无聊,所以他们给出了两个分别长为 n,m 的序列 a,b。结束游戏时,若车当前位于 (x,y),则游戏的分数为 ax+by,Alice 想让游戏的分数尽量小,而 Bob 想让游戏的分数尽量大。你需要求出在双方的最优策略下,游戏的分数是多少。
输入格式
第一行两个整数 n,m 表示棋盘大小。
第二行 n 个整数 ai,表示序列 a。
第三行 m 个整数 bi,表示序列 b。
输出格式
输出一行一个整数,表示答案。
样例输入 1
2 1
3 2
2
样例输出 1
4
样例输入 2
6 7
4 5 6 1 2 3
5 2 1 3 4 6 7
样例输出 2
7
样例解释
样例 1 中如果双方要移动,那么目标都是唯一确定的,而 Bob 在他的第 109−1 轮中移动时发现此时会将格子 (1,1) 经过的次数变为 109,而这不是合法的操作。所以 Bob 只能在他的某次操作中选择结束游戏,游戏的分数即为 a2+b1=4。
样例 2 的决策树大小至少为 5109 量级,这里空太小,画不开。
数据范围
对于所有数据,1≤n,m≤2×105,1≤ai,bi≤108。
子任务 1(14 分):n,m≤4。
子任务 2(11 分):bi=1。
子任务 3(15 分):n,m≤10。
子任务 4(16 分):n,m≤103。
子任务 5(19 分):n,m≤5×104。
子任务 6(25 分):无特殊限制。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
2 1
3 2
2
4
样例 2
6 7
4 5 6 1 2 3
5 2 1 3 4 6 7
7