算法

(暴力枚举、排序)

$$ \begin{aligned} &\max(\mid x \mid + \mid y \mid + \mid z \mid) \\\ =& \max(x+y+z, x+y-z, x-y+z, x-y-z, -x+y+z, -x+y-z, -x-y+z, -x-y-z) \end{aligned} $$

所以对于原问题我们只需对 $\{x+y-z\},\ \{z+y-z\},\ \cdots, \ \{-x-y-z\}$ 这些序列分别求出他们前 $M$ 大的数的和，然后对这八个值取最大值即可。

Python 代码

n, m = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]

def solve():
    d = [0] * n
    for i in range(n):
        for j in range(3):
            d[i] += a[i][j]
    d.sort()
    return sum(d[n - m:])

ans = 0
for di in range(2):
    for i in range(n):
        a[i][0] *= -1
    for dj in range(2):
        for i in range(n):
            a[i][1] *= -1
        for dk in range(2):
            for i in range(n):
                a[i][2] *= -1
            ans = max(ans, solve())
print(ans)

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::max;
using std::vector;
using ll = long long;

int main() {
    int n, m;
    cin >> n >> m;

    vector a(n, vector<ll>(3));
    rep(i, n)rep(j, 3) cin >> a[i][j];

    auto solve = [&]() {
        vector<ll> d(n);
        rep(i, n)rep(j, 3) d[i] += a[i][j];
        sort(d.rbegin(), d.rend());
        ll curSum = 0;
        rep(i, m) curSum += d[i];
        return curSum;
    };

    ll ans = 0;
    rep(di, 2) {
        rep(i, n) a[i][0] *= -1;
        rep(dj, 2) {
            rep(i, n) a[i][1] *= -1;
            rep(dk, 2) {
                rep(i, n) a[i][2] *= -1;
                ll now = solve();
                ans = max(ans, now);
            }
        }
    }

    cout << ans << '\n';

    return 0;
}