AtCoder ABC100D Patisserie ABC

Problem Statement

Takahashi became a pastry chef and opened a shop La Confiserie d’ABC to celebrate AtCoder Beginner Contest 100.

The shop sells NN kinds of cakes.
Each kind of cake has three parameters “beauty”, “tastiness” and “popularity”. The $i$-th kind of cake has the beauty of $x_i$, the tastiness of $y_i$ and the popularity of $z_i$.
These values may be zero or negative.

Ringo has decided to have MM pieces of cakes here. He will choose the set of cakes as follows:

• Do not have two or more pieces of the same kind of cake.
• Under the condition above, choose the set of cakes to maximize (the absolute value of the total beauty) + (the absolute value of the total tastiness) + (the absolute value of the total popularity).

Find the maximum possible value of (the absolute value of the total beauty) + (the absolute value of the total tastiness) + (the absolute value of the total popularity) for the set of cakes that Ringo chooses.

Constraints

• $N$ is an integer between $1$ and $1 000$ (inclusive).
• $M$ is an integer between $0$ and $N$ (inclusive).
• $x_i$, $y_i$, $z_i$ ($1≤i≤N$) are integers between $−10 000 000 000$ and $10 000 000 000$ (inclusive).

Input

Input is given from Standard Input in the following format:

$N$ $M$
$x_1$ $y_1$ $z_1$
$x_2$ $y_2$ $z_2$
$::$ $::$
$x_N$ $y_N$ $z_N$

Output

Print the maximum possible value of (the absolute value of the total beauty) + (the absolute value of the total tastiness) + (the absolute value of the total popularity) for the set of cakes that Ringo chooses.

Sample Input 1

5 3
3 1 4
1 5 9
2 6 5
3 5 8
9 7 9

Sample Output 1

56

Consider having the $2$-nd, $4$-th and $5$-th kinds of cakes. The total beauty, tastiness and popularity will be as follows:

• Beauty: $1+3+9=13$
• Tastiness: $5+5+7=17$
• Popularity: $9+8+9=26$

The value (the absolute value of the total beauty) + (the absolute value of the total tastiness) + (the absolute value of the total popularity) here is $13+17+26=56$. This is the maximum value.

Sample Input 2

5 3
1 -2 3
-4 5 -6
7 -8 -9
-10 11 -12
13 -14 15

Sample Output 2

54

Consider having the $1$-st, $3$-rd and $5$-th kinds of cakes. The total beauty, tastiness and popularity will be as follows:

• Beauty: $1+7+13=21$
• Tastiness: $(−2)+(−8)+(−14)=−24$
• Popularity: $3+(−9)+15=9$

The value (the absolute value of the total beauty) + (the absolute value of the total tastiness) + (the absolute value of the total popularity) here is $21+24+9=54$. This is the maximum value.

Sample Input 3

10 5
10 -80 21
23 8 38
-94 28 11
-26 -2 18
-69 72 79
-26 -86 -54
-72 -50 59
21 65 -32
40 -94 87
-62 18 82

Sample Output 3

638

If we have the $3$-rd, $4$-th, $5$-th, $7$-th and $10$-th kinds of cakes, the total beauty, tastiness and popularity will be $−323$, $66$ and $249$, respectively.
The value (the absolute value of the total beauty) + (the absolute value of the total tastiness) + (the absolute value of the total popularity) here is $323+66+249=638$. This is the maximum value.

Sample Input 4

3 2
2000000000 -9000000000 4000000000
7000000000 -5000000000 3000000000
6000000000 -1000000000 8000000000

Sample Output 4

30000000000

The values of the beauty, tastiness and popularity of the cakes and the value to be printed may not fit into 32-bit integers.

Idea

设所有蛋糕的下标集合为 $V_N$，被挑选的蛋糕下标集合为 $V_M$，则 $V_M\subset V_N$。最后的价值为 $\left|\sum\limits_{i\in V_M}x_i\right|+\left|\sum\limits_{i\in V_M}y_i\right|+\left|\sum\limits_{i\in V_M}z_i\right|$，枚举 $\sum\limits_{i\in V_M}x_i$、$\sum\limits_{i\in V_M}y_i$、$\sum\limits_{i\in V_M}z_i$ 三项的符号，共 $8$ 种情况。

用 $3$ 个二进制位表示情况，$0$ 表示正号，$1$ 表示负号。对于一种特定的情况，我们可以知道 $N$ 个蛋糕中每个蛋糕对最后价值的贡献：比如三项的符号分别为负、负、正，第 $i$ 个蛋糕的贡献为 $-x_i-y_i+z_i$；当 $x_i>0$，其Beauty属性的贡献实际是负的，其他属性类似。枚举所有情况，对于每一种情况，取贡献最大的 $m$ 个蛋糕，然后更新最大值即可。

这是一种类似反证法的思想：假设最终的情况，当另一种情况比当前情况的价值更大时，就说明当前假设失败。

Code

#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
const int MAX_SIZE = 1000;
ll value[MAX_SIZE][3];
int n, m;
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		scanf("%lld%lld%lld", &value[i][0], &value[i][1], &value[i][2]);
	}
	ll ans = LLONG_MIN;
	for (int choice = 0; choice < 8; choice++) {
		vector<ll>contribution(n);
		for (int i = 0; i < n; i++) {
			for (int k = 0; k < 3; k++) {
				if ((choice >> k) & 1) {
					contribution[i] -= value[i][k];
				} else {
					contribution[i] += value[i][k];
				}
			}
		}
		sort(contribution.begin(), contribution.end(), greater <ll>());
		ll res = 0;
		for (int i = 0; i < m; i++) {
			res += contribution[i];
		}
		ans = max(ans, res);
	}
	cout << ans << endl;
	return 0;
}