← 返回题目列表

Codeforces · 2051/G

G. 蛇

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

假设您玩的游戏中,游戏区域看起来像一条 $$$1 \times 10^9$$$ 方形单元格,编号从 $$$1$$$ 到 $$$10^9$$$。

你有 $$$n$$$ 条蛇(编号从 $$$1$$$ 到 $$$n$$$)需要放入一些单元格中。最初,每条蛇恰好占据一个单元格,并且您不能将多于一条的蛇放入一个单元格中。之后,游戏开始。

游戏持续 $$$q$$$ 秒。每秒可能发生两种类型的事件:

-snake $$$s_i$$$放大:如果snake $$$s_i$$$占据了单元格$$$[l, r]$$$,它会放大为一段$$$[l, r + 1]$$$;
-snake $$$s_i$$$ 收缩:如果snake $$$s_i$$$ 占据了单元格$$$[l, r]$$$,它会收缩为一段$$$[l + 1, r]$$$。

每一秒,都会发生一个事件。

如果在任何时刻,任何蛇遇到某个障碍物(另一条蛇或带子的末端),您就输了。否则,您获胜的分数等于迄今为止任何蛇占据的最大单元格。

您能达到的最低分数是多少?

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n \le 20$$$; $$$1 \le q \le 2 \cdot 10^5$$$) — 蛇的数量和事件的数量。接下来的 $$$q$$$ 行包含事件的描述 - 每行一个。

第 $$$i$$$ 行包含

- “$$$s_i$$$ +” ($$$1 \le s_i \le n$$$) 表示第 $$$s_i$$$ 条蛇放大
- 或“$$$s_i$$$ -” ($$$1 \le s_i \le n$$$) 表示第 $$$s_i$$$ 条蛇缩小。

对输入的附加约束:给定的事件序列有效,i。 e.长度为 $$$1$$$ 的蛇永远不会缩小。

输出

打印一个整数——可能的最低分数。

示例

输入 #1

3 6
1 +
1 -
3 +
3 -
2 +
2 -

输出 #1

4

输入 #2

5 13
5 +
3 +
5 -
2 +
4 +
3 +
5 +
5 -
2 +
3 -
3 +
3 -
2 +

输出 #2

11

注意

在第一个测试中,最佳策略是将第二条蛇放置在单元格 $$$1$$$ 处,第三条蛇放置在 $$$2$$$ 处,第一条蛇放置在 $$$3$$$ 处。最大占用的单元格是单元格$$$4$$$,并且它是可能的最小分数。

在第二个测试中,最佳策略之一是放置:

- 蛇 $$$2$$$ 位于 $$$1$$$ 位置;
- 蛇 $$$3$$$ 位于 $$$4$$$ 位置;
- 蛇 $$$5$$$ 位于 $$$6$$$ 位置;
- 蛇 $$$1$$$ 位于 $$$9$$$ 位置;
- 蛇 $$$4$$$ 位于 $$$10$$$ 位置。