[ABC100D] Patisserie ABC-Toy模板网

这篇具有很好参考价值的文章主要介绍了[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 N kinds of cakes.
Each kind of cake has three parameters "beauty", "tastiness" and "popularity". The i-th kind of cake has the beauty of xi, the tastiness of yi and the popularity of zi.
These values may be zero or negative.

Ringo has decided to have M 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 11 and 1 0001 000 (inclusive).

M is an integer between 00 and N (inclusive).

xi,yi,zi (1≤i≤N) are integers between −10 000 000 000−10 000 000 000 and 10 000 000 00010 000 000 000 (inclusive).

Input

Input is given from Standard Input in the following format:
N M
1x1 1y1 1z1
2x2 2y2 2z2
 ::  ::
xN yN zN
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 Copy

Copy
5 3
3 1 4
1 5 9
2 6 5
3 5 8
9 7 9
Sample Output 1 Copy

Copy
56
Consider having the 22-nd, 44-th and 55-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=5613+17+26=56. This is the maximum value.

Sample Input 2 Copy

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

Copy
54
Consider having the 11-st, 33-rd and 55-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 Copy

Copy
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 Copy

Copy
638
If we have the 3-rd, 4th, 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 Copy

Copy
3 2
2000000000 -9000000000 4000000000
7000000000 -5000000000 3000000000
6000000000 -1000000000 8000000000
Sample Output 4 Copy

Copy
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.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <unordered_set>
#include <unordered_map>
using namespace std;
#define endl '\n'
#define int long long
typedef pair<int,int>PII;
constexpr int N = 2,mod=1e9+7;

struct node{
    int a,b,c;
}p[1005];
int i,j,k;
bool cmp(node a,node b){
    return a.a*i+a.b*j+a.c*k>b.a*i+b.b*j+b.c*k;
}
signed main()
{
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,m;
    cin>>n>>m;
    for( i=1;i<=n;i++){
        cin>>p[i].a>>p[i].b>>p[i].c;
    }
    int res=-1e17;
    for( i=-1;i<=1;i+=2){
        for( j=-1;j<=1;j+=2){
            for( k=-1;k<=1;k+=2){
                sort(p+1,p+n+1,cmp);
                int ans1=0,ans2=0,ans3=0;
                for( int s=1;s<=m;s++){
                    ans1+=p[s].a;
                    ans2+=p[s].b;
                    ans3+=p[s].c;
                }
                res= max(res, (ans1*i+ans2*j+ans3*k));
            }
        }
    }
    cout<<res<<endl;
    return 0;
}

文章来源地址https://www.toymoban.com/news/detail-410344.html

到了这里，关于[ABC100D] Patisserie ABC的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！