题面

原题面
我来概括一下:
给出 $n \in [1, 1e5]$ 个五元组,要求选出 $k \in [1, n]$ 个合成后权值最大。
我们定义一个五元组的权值为它的五个元素之和。
我们定义两个五元组的合成为他们对应元素取最大值后得到的一个五元组。
比如 $[1, 2, 3, 4, 5]$ 与 $[5, 4, 3, 2, 1]$ 的合成为 $[5, 4, 3, 4, 5]$,它的权值为 $5 + 4 + 3 4 + 5 = 21$

题解

一个五元组对答案的贡献就是它里面的一些元素成为最大值。比如一个五元组的一、三元素在答案方案中为最大值,那么将它表示为10100。进一步的例子,一个答案的方案可能由两个五元组组成:
10100
01011
但是我们不清楚究竟是哪两个五元组。
所以不妨对所有的五元组都按10100的方式算出来对应位置元素的和,取他们的最大值。=
对01011也是这样。
把两个最大值加起来就是“假如答案这样组成”的答案。
所以我们枚举答案的组成方式即可。
也就是枚举11111的子集。
代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using std::max;
const int N = 1e5 + 1;
int a[N][5], rec[1 << 5], n, k, ans;
void dfs(int p, int d, int s) {
    if (d == k) ans = max(ans, s);
    else for (int i = p; i; i = (i-1)&p)
        dfs(p^i, d + 1, s + rec[i]);
}
int main() {
    int T; scanf("%d", &T);
    while (T--) {
        memset(rec, 0, sizeof(rec));
        ans = 0;
        scanf("%d%d",&n, &k);
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < 5; j++) scanf("%d", &a[i][j]);
            for (int c = 0, s = 0; c < 1 << 5; rec[c] = max(rec[c], s), s = 0, c++)
                 for (int x = 0; x < 5; x++) s += ((c&(1 << x)) ? 1 : 0)*a[i][x];
        }
        dfs(31, 0, 0);
        printf("%d\n", ans);
    }
}