{"problem":{"name":"[PA 2024] Autostrada 2","description":{"content":"**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 5 [Autostrada 2](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/aut/)** 经过多年毫无意义的战争之后，Byteotia 和 Bitotia 终于签署了和平条约。作为最终协议的标志，两国首府之间修建","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":4000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10362"},"statements":[{"statement_type":"Markdown","content":"**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 5 [Autostrada 2](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/aut/)**\n\n经过多年毫无意义的战争之后，Byteotia 和 Bitotia 终于签署了和平条约。作为最终协议的标志，两国首府之间修建了一条高速公路。而你则被任命为这条高速公路从 Byteotia 到 Bitotia 方向的管理者（至于从 Bitotia 到 Byteotia 方向，你并不感兴趣，它由~~不~~友好国家的管理者管理）。\n\n高速公路上目前有 $m$ 个收费站，编号为 $1$ 到 $m$。在一天的不同时段，通过某个收费站的费用会有所不同。一天分为 $n$ 个小时，编号为 $1$ 到 $n$。目前，在第 $i$ 个小时通过第 $j$ 个收费站的花费为 $c_{i,j}$ bytealerts。其中一些成本可能为 $0$（此时收费站免费），甚至为负（此时司机通过收费站会获得 $-c_{i,j}$ bytealerts）。\n\n整条高速公路很短，一小时就能走完。当然，你也不必如此匆忙，你可以在行驶过程中随意停车。不过，你不能在高速公路上过夜，必须在当天通过所有收费站。\n\n当然，司机希望以尽可能低的花费通过高速公路。对于 $1 \\le i \\le j \\le n$，我们用 $f(i,j)$ 表示司机在第 $i$ 小时通过第一个收费站，并在第 $j$ 小时通过最后一个收费站的情况下，通过整条高速公路的最小可能花费。所有 $f(i,j)$ 都是被两国政府的和平条约提前设置好的，作为高速公路管理者你不能更改他们。\n\n但是，只要保证保留第一个和最后一个收费站，$f(i, j)$ 的值保持不变，并且设置的所有费用都是 $1$ bytealert 的整数倍的情况下，你可以自由修改通过各个收费站的花费，甚至取消某些收费站。\n\n为了最小化高速公路维护的费用，你希望取消尽可能多的收费站。确定为了满足条约内容，最少需要保留多少收费站。\n\n收费计划重组项目将分为两个阶段。在第一阶段，即初步设计阶段，只需找到最佳的收费站数量即可。但在第二阶段，即项目实施阶段，你还需要提供一份完整的收费站价格表计划。\n\n## Input\n\n第一行三个整数 $n,m,q\\ (2\\le n,m\\le 30\\,000,n\\cdot m\\le 300\\,000,q\\in \\{0,1\\})$，分别表示一天中的小时数，收费站数和描述项目阶段的一位。$q=0$ 表示项目处于第一阶段（初步设计），$q=1$ 表示项目处于第二阶段（实施阶段）。\n\n接下来 $n$ 行描述目前的收费情况，第 $i$ 行包含 $m$ 个整数 $c_{i,1},c_{i,2},\\ldots,c_{i,m}\\ (-10^6\\le c_{i,j}\\le 10^6)$，意义如题目描述。\n\n## Output\n\n第一行输出一个整数 $k\\ (2\\le k\\le m)$，表示最少需要保留多少收费站，才能满足没有 $f(i,j)$ 改变。如果 $q=0$，输出仅包含这一行一个整数。\n\n如果 $q=1$，接下来 $n$ 行输出满足题目条件的最优价格计划。第 $i$ 行包含 $k$ 个整数 $d_{i,1},d_{i,2},\\ldots,d_{i,k}\\ (-10^{12}\\le d_{i,j}\\le 10^{12})$。$d_{i,j}$ 表示在第 $i$ 小时通过第 $j$ 个收费站的新花费。\n\n可以从题目限制知道，总可以确定一个绝对值不超过 $10^{12}$ 且花费均为整数的计划。\n\n[samples]\n\n## Background\n\nPA 2024 5A1\n（缺 SPJ）\n\n## Note\n\n第一个样例中，$f(i,j)$ 如下：\n$$f(1, 1) = (-1) + 0 + 4 + 0 + (-3) + 0 = 0$$\n$$f(1, 2) = (-1) + 0 + 4 + 0 + (-5) + 2 = 0$$\n$$f(1, 3) = (-1) + 0 + 4 + 0 + (-5) + 2 = 0$$\n$$f(2, 2) = (-4) + 1 + 5 + 2 + (-5) + 2 = 1$$\n$$f(2, 3) = (-4) + 1 + 3 + 0 + (-2) + 2 = 0$$\n$$f(3, 3) = (-5) + 2 + 3 + 0 + (-2) + 2 = 0$$\n\n两个收费站无法实现相同的花费。请注意，第一个和最后一个收费站是不能取消的，尽管根据输出的 $d_{i,j}$ 费用，这两个收费站是不收费的。\n\n在第二个样例中，由于收费计划重组草案仅处于初步阶段，因此输出不包含新价目表的计划。\n\n**数据范围与提示**\n\n- 有一半的子任务满足 $q=0$。\n- 另一半子任务满足 $q=1$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10362","tags":["2024","PA（波兰）"],"sample_group":[["3 6 1\n-1 0 4 0 -3 0\n-4 1 5 2 -5 2\n-5 2 3 0 -2 2\n","3\n0 0 0\n0 1 0\n0 0 0\n"],["5 7 0\n0 0 0 8 0 0 0\n0 7 6 5 9 7 0\n0 0 0 5 9 6 0\n9 4 0 4 4 7 0\n0 0 0 9 8 6 0\n","3"]],"created_at":"2026-03-03 11:09:25"}}