#A. [JOISC2022] 团队竞技

    Type: RemoteJudge 2000ms 1024MiB

[JOISC2022] 团队竞技

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

JOISC2022 D2T3

题目描述

JOI 大学有 NN 只海狸,他们都参与竞技编程。每只海狸有三项能力值:思考值,行动值和运气值。如果一个能力值很大,意味着他这项能力比较强大。对于第 i (i[1,N])i~(i\in[1,N]) 只海狸,他的思考值为 XiX_i,行动值为 YiY_i,运气值为 ZiZ_i

今年 JOI 大学的海狸们将参与一场团体竞技编程,一支队伍由三名队员组成。Bitaro 是 JOI 大学的教练,由于团队合作很重要,Bitaro 决定从 NN 只海狸中选出三只海狸组成队伍,这三只海狸要满足以下条件:

条件:每个成员都有自己的优势,这意味着每个成员都有一项能力值严格大于其他两人的对应能力值。

在所有符合条件的组队中,Bitaro 想要选一个总能力最强的队伍,一个队伍的总能力定义为:三人最大思考值,三人最大行动值和三人最大运气值之和。

请你求出,是否存在一个符合条件的组队,如果是,计算队伍总能力可能的最大值。

输入格式

第一行一个整数 NN 表示海狸数。

接下来 NN 行每行三个整数 Xi,Yi,ZiX_i,Y_i,Z_i 表示海狸的各项能力值。

输出格式

一行一个整数,如果不存在符合条件的组队,输出 -1,否则输出队伍总能力的最大值。

5
3 1 4
2 3 1
1 5 5
4 4 2
5 2 3
13
8
1 1 1
1 1 5
1 5 1
5 1 1
1 5 5
5 1 5
5 5 1
5 5 5
15
4
1 2 3
1 2 3
1 2 3
1 2 3
-1

提示

【样例解释 #1】

由海狸 1,4,51,4,5 组成的队伍符合条件,因为:

  1. 海狸 11 的优势是运气。
  2. 海狸 44 的优势是行动。
  3. 海狸 55 的优势是思考。

总能力值为:5+4+4=135+4+4=13

可以证明这是符合条件的组队中,总能力值最高的队伍。

注意如果选择海狸 1,3,51,3,5,总能力值将达到 1515,但是这会导致海狸 11 没有特长。

这组样例满足所有子任务的限制。

【样例解释 #2】

最优组队为:海狸 2,3,42,3,4

这组样例满足所有子任务的限制。

【样例解释 #3】

任何组队方式都会导致队员没有特长,不存在符合条件的组队。

这组样例满足所有子任务的限制。

【数据范围】

对于所有数据,满足:

  • 3N1500003\leq N\leq 150000
  • 1Xi,Yi,Zi1081\leq X_i,Y_i,Z_i\leq 10^8 (1iN)(1\leq i\leq N)

详细子任务附加限制及分值如下表所示:

子任务编号 附加限制 分值
11 N300N\leq 300 88
22 N4000N\leq 4000 2929
33 Xi,Yi,Zi5X_i,Y_i,Z_i\leq 5 (i[1,N])(i\in[1,N]) 99
44 Xi,Yi,Zi20X_i,Y_i,Z_i\leq 20 (i[1,N])(i\in[1,N])
55 Xi,Yi,Zi300X_i,Y_i,Z_i\leq 300 (i[1,N])(i\in[1,N])
66 Xi,Yi,Zi4000X_i,Y_i,Z_i\leq 4000 (i[1,N])(i\in[1,N])
77 无附加限制 2727

20240116杂题选讲

Not Attended
Status
Done
Rule
IOI
Problem
6
Start at
2024-1-16 18:00
End at
2024-1-18 18:00
Duration
48 hour(s)
Host
Partic.
25