说明

\\n\\n小 L 是学校算法协会的成员。在今年的学校社团招新中，小 L 一共招收了 $n$ 个新成员，其中 $n$ 为偶数。现在小 L 希望将他们分到协会不同的部门。 \\n\\n算法协会共设有三个部门，其中第 $i$ ($1 \\\\leq i \\\\leq n$) 个新成员对第 $j$ ($1 \\\\leq j \\\\leq 3$) 个部门的满意度为 $a_{i,j}$。定义一个分配方案的满意度为所有新成员对分配到的部门的满意度之和，也就是说，若将第 $i$ ($1 \\\\leq i \\\\leq n$) 个新成员分配到了第 $d_i \\\\in \\\\{1,2,3\\\\}$ 个部门，则该分配方案的满意度为 $\\\\sum_{i=1}^{n} a_{i,d_i}$。 \\n\\n小 L 不希望某一个部门的新成员数量过多。具体地，他要求在分配方案中，不存在一个部门被分配多于 $\\\\frac{n}{2}$ 个新成员。你需要帮助小 L 求出，满足他要求的分配方案的满意度的最大值。\\n\\n

输入格式

\\n\\n本题包含多组测试数据。 \\n\\n输入的第一行包含一个正整数 $t$，表示测试数据组数。 \\n\\n接下来依次输入每组测试数据，对于每组测试数据： \\n\\n- 第一行包含一个正整数 $n$，表示新成员的数量。 \\n- 第 $i+1$ ($1 \\\\leq i \\\\leq n$) 行包含三个非负整数 $a_{i,1}, a_{i,2}, a_{i,3}$，分别表示第 $i$ 个新成员对第 $1,2,3$ 个部门的满意度。\\n\\n

输出格式

\\n\\n对于每组测试数据，输出一行一个非负整数，表示满足小 L 要求的分配方案的满意度的最大值。\\n\\n

样例

\\n\\n

状态	递交者	时间	内存	语言	代码	递交时间
AC	邓泊修	1084ms	16.4 MiB	C++14(O2)	1.1 KiB	2026-10-13 23:47:19
AC	曹卓琦	1207ms	17.3 MiB	C++17(O2)	1.9 KiB	2026-8-11 17:00:32
AC	张泊文	1559ms	17.3 MiB	C++20(O2)	1.7 KiB	2026-8-13 23:28:48

统计

递交统计

[CSP-S 2025] 社团招新

信息

状态

开发

支持

关于

登录