← 返回题目列表

AtCoder · jag2016secretspring_d

D. 隐形

中文机器翻译题面 查看原题

问题陈述

你要和朋友一起インビジブル玩一种叫做“”的卡牌游戏。 在这个卡牌游戏中,得点カード“和”妨害カード”。 每张记分卡上都写有一个正值。该纸牌游戏的规则如下。

  • 游戏由两名玩家(玩家 1 和玩家 2)进行。游戏从玩家 1 的回合开始。
  • 游戏中有一堆和两副牌。该叠牌由两名玩家放置的牌组成。此外,每个玩家的牌组由玩家拥有的记分卡和干扰卡组成。玩家可以随时检查自己或对手牌组中的牌的顺序。游戏开始时,牌堆中没有牌。
  • 两名玩家轮流执行以下两个动作之一,恰好一次。
    • 将你牌库顶牌置于牌堆顶部。然而,如果你的牌组中没有牌,则无法执行此操作。
    • 轮到你了。
  • 当玩家经过一个回合时,执行以下处理。
    • 每位玩家获得堆叠中满足以下两个条件的所有计分卡: 获得的计分卡从游戏中移除。
      1. 这是您放入堆叠中的记分卡。
      2. 高于对手放置的所有干扰卡(当堆叠中没有对手干扰卡时,玩家获得他或她放置在堆叠中的所有卡)。
    • 从牌堆中取出所有牌。

如果两名玩家连续过牌且牌堆上没有牌,则游戏结束。 每个玩家的最终得分是每个玩家记分卡上所写数字的总和。

每个玩家采取最优行动,使自己的分数减去对手的分数所获得的值最大化。 您的任务是根据每个玩家的牌组,计算当每个玩家表现最佳时,玩家 1 的分数和玩家 2 的分数之间的差异。


输入

输入由以下形式的单个测试用例组成:

$n$ $m$
$a_1$ $a_2$ $\点$ $a_n$
$b_1$ $b_2$ $\点$ $b_m$

第一行由正整数 $n$、$m$ ($1 \le n, m \le 50$) 组成,表示这副牌中的牌数。 第二行由 $n$ 个整数组成,其中 $a_i$ 表示玩家 1 牌组顶部的第 $i$ 张牌 ($1 \le i \le n$)。 $a_i$ 大于或等于 $1$ 且小于或等于 $1{,}000{,}000$ 或 $-1$。 第三行由 $m$ 个整数组成,其中 $b_j$ 表示玩家 2 牌组顶部的第 $j$ 张牌 ($1 \le j \le m$)。 $b_j$ 大于或等于 $1$ 且小于或等于 $1{,}000{,}000$ 或 $-1$。 当$a_i$和$b_j$为正整数时,代表记分卡,当$-1$时,代表干扰卡。

输出

当两个玩家都表现最佳时,输出(玩家 1 的得分)-(玩家 2 的得分)。



示例输入 1

2 2
100 -1
200 300

样本输入 1 的输出

-100



示例输入 2

3 5
10 30 -1
-1 90 20 10 -1

样本输入 2 的输出

0

示例输入 3

4 5
15 20 10 30
50 30 10 20 25

样本输入 3 的输出

-60