街机游戏机 - 题目

小 Vitechka 和他的 $n - 1$ 个朋友来到了电子游戏厅。这里有 $m$ 台游戏机。

这 $n$ 个人中的每一个人都立刻决定了自己想在 $m$ 台游戏机中的每一台上玩多少分钟。现在他们希望尽可能快地玩完，以便有足够的时间去电影院看电影。

请帮助他们制定一个最优策略。

每个人在同一时刻最多只能玩一台游戏机，且每台游戏机在同一时刻最多只能被一个人玩。每个人可以随时暂停在某台游戏机上的游玩，并在稍后重新开始，次数不限：只有在每台游戏机上的总游玩时间是重要的。

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 120$）。

接下来的 $n$ 行中，每行包含 $m$ 个不超过 $10^9$ 的非负整数。第 $i+1$ 行的第 $j$ 个数等于第 $i$ 个人想要玩第 $j$ 台游戏机的分钟数。

将策略输出为若干个阶段。一个阶段定义了玩家在游戏机之间的分配以及为该阶段分配的时间。这种阶段的数量不能超过 $2 \cdot 10^4$。

在第一行中，输出两个整数 $t$ 和 $k$：游戏进行所需的最短可能时间以及阶段的数量。

接下来的 $k$ 行中，每行必须描述一个阶段。每个阶段的描述必须以一个非负整数开始：为该阶段分配的分钟数。之后，输出 $n$ 个整数定义分配方案。其中的第 $i$ 个数必须等于第 $i$ 个人在整个阶段期间所玩的机器编号，如果该人在整个阶段期间不玩游戏，则为 $0$。

在你的策略执行完毕后，每个人在每台机器上玩的分钟数必须恰好等于他想玩的分钟数。

2 3
0 1 2
4 0 0

QOJ.ac