{"problem":{"name":"[THUSC 2021] Emiya 家明天的饭","description":{"content":"Emiya 是个擅长做菜的高中生，他会做 $m$ 道不同的菜品。某天，Yaz、Zid 和他们的 $n$ 个朋友们到他家做客，Emiya 需要做一些菜来招待他们。 Yaz 和 Zid 什么都吃，但他们的朋友们有些挑食。具体来说，我们用整数 $a_{i,j}\\geq -1$ 来表示第 $i$ 个朋友对第 $j$ 道菜品的态度： * 若 $a_{i,j}\\geq 0$，则第 $i$ 位朋友不讨厌这道","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2500,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10242"},"statements":[{"statement_type":"Markdown","content":"Emiya 是个擅长做菜的高中生，他会做 $m$ 道不同的菜品。某天，Yaz、Zid 和他们的 $n$ 个朋友们到他家做客，Emiya 需要做一些菜来招待他们。\n\nYaz 和 Zid 什么都吃，但他们的朋友们有些挑食。具体来说，我们用整数 $a_{i,j}\\geq -1$ 来表示第 $i$ 个朋友对第 $j$ 道菜品的态度：\n\n* 若 $a_{i,j}\\geq 0$，则第 $i$ 位朋友不讨厌这道菜品，如果饭桌上有这道菜，且没有其他让这位朋友讨厌的菜品，那么他会给 Emiya 留下 $a_{i,j}$ 元红包以表赞许和感谢。\n\n* 若 $a_{i,j} = -1$，则第 $i$ 为朋友讨厌这道菜品，如果饭桌上有这道菜，那么这位朋友会非常生气，并直接离席而去。这意味着他将不会因为任何菜品留下红包。\n\nEmiya 擅长做菜，却不擅长计算，请你帮助 Emiya 挑选若干道菜品，使得他收到的红包数额总和最大。方便起见，你只需要输出这个最大的总和即可。\n\n## Input\n\n第一行包含两个整数 $n,m$，意义见题目描述。\n\n第 $2$ 到第 $n+1$ 行，每行包含 $m$ 个整数：其中第 $i+1$ 行的第 $j$ 个整数为 $a_{i,j}$，意义见题目描述。\n\n保证 $n,m\\geq 1$，保证 $a_{i,j} \\geq -1$。\n\n## Output\n\n一行一个整数，表示红包金额的最大总和。\n\n[samples]\n\n## Background\n\n由于本题的测试数据规模较大，本题只评测一部分测试数据，其余的测试数据可以在 [U412486](https://www.luogu.com.cn/problem/U412486) 中提交测试。\n\n## Note\n\n**【样例解释 #1】**\n\n最优方案是制作第 $1$ 和第 $2$ 道菜。若如此做，虽然第 $2$ 位客人会生气地离席而去，但另两位客人留下的红包总金额是最大的。\n\n**【子任务】**\n\n本题设置 4 个子任务：\n\n* 第 1 个子任务（20 分）的特殊限制：$n\\leq 10, m\\leq 2000$；\n* 第 2 个子任务（20 分）的特殊限制：$n\\leq 14$；\n* 第 3 个子任务（20 分）的特殊限制：每位朋友不喜欢的菜品编号范围为一个区间，即对于每位客人 $i$，存在整数 $l,r$（$l\\leq r$），满足 $a_{i,j} = -1$ 当且仅当 $j\\in \\left[l,r\\right]$；\n* 第 4 个子任务（40 分）没有特殊限制。\n\n对于所有测试点，保证 $n\\leq 20$，$m\\leq 10^6$，$a_{i,j}\\leq 10^9$。\n\n**【提示】**\n\n一些测试点的输入规模较大，请注意程序的 IO 效率。\n\n### 题目使用协议\n\n来自 清华大学 2021 年全国优秀中学生信息学体验营 (THUSC 2021)。\n\n以下『本仓库』皆指 THUSC 2021 官方仓库（[https://gitlink.org.cn/thusaa/thusc2021](https://gitlink.org.cn/thusaa/thusc2021)）\n\n1. 任何单位或个人都可以免费使用或转载本仓库的题目；\n2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；\n3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库地址。\n4. 清华大学计算机系保留一切权利。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10242","tags":["动态规划 DP","2021","O2优化","快速沃尔什变换 FWT","THUSC","状压 DP"],"sample_group":[["3 3\n1 2 3\n2 -1 100\n100 10 -1\n","113\n"],["见附件中的 2.in。","见附件中的 2.ans。"],["见附件中的 3.in。","见附件中的 3.ans。"]],"created_at":"2026-03-03 11:09:25"}}