AT_abc391_f.[ABC391F] K-th Largest Triplet

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$ 、 $B=(B_1,B_2,\ldots,B_N)$ 、 $C=(C_1,C_2,\ldots,C_N)$ 以及整数 $K$ 。

对于所有满足 $1 \leq i,j,k \leq N$ 的整数三元组 $(i,j,k)$ 的 $N^3$ 种选择方式，计算 $A_iB_j + B_jC_k + C_kA_i$ 的值。请输出这些值中从大到小第 $K$ 个的值。

输入格式

输入通过标准输入按以下格式给出：

$N$ $K$
$A_1$ $A_2$ $\ldots$ $A_N$
$B_1$ $B_2$ $\ldots$ $B_N$
$C_1$ $C_2$ $\ldots$ $C_N$

输出格式

输出答案。

输入输出样例

输入#1
```
2 5
1 2
3 4
5 6
```
输出#1
```
31
```

输入#2

3 10
100 100 100
100 100 100
100 100 100

输出#2

输入#3

5 54
800516877 573289179 26509423 168629803 696409999
656737335 915059758 201458890 931198638 185928366
140174496 254538849 830992027 305186313 322164559

输出#3

689589940713840351

说明/提示

约束条件

$1 \leq N \leq 2 \times 10^5$
$1 \leq K \leq \min(N^3, 5 \times 10^5)$
$1 \leq A_i, B_i, C_i \leq 10^9$
输入均为整数

样例解释 1

$N^3=8$ 个整数的值如下：

$(i,j,k)=(1,1,1)$ ： $A_1B_1 + B_1C_1 + C_1A_1 = 1 \times 3 + 3 \times 5 + 5 \times 1 = 23$
$(i,j,k)=(1,1,2)$ ： $A_1B_1 + B_1C_2 + C_2A_1 = 1 \times 3 + 3 \times 6 + 6 \times 1 = 27$
$(i,j,k)=(1,2,1)$ ： $A_1B_2 + B_2C_1 + C_1A_1 = 1 \times 4 + 4 \times 5 + 5 \times 1 = 29$
$(i,j,k)=(1,2,2)$ ： $A_1B_2 + B_2C_2 + C_2A_1 = 1 \times 4 + 4 \times 6 + 6 \times 1 = 34$
$(i,j,k)=(2,1,1)$ ： $A_2B_1 + B_1C_1 + C_1A_2 = 2 \times 3 + 3 \times 5 + 5 \times 2 = 31$
$(i,j,k)=(2,1,2)$ ： $A_2B_1 + B_1C_2 + C_2A_2 = 2 \times 3 + 3 \times 6 + 6 \times 2 = 36$
$(i,j,k)=(2,2,1)$ ： $A_2B_2 + B_2C_1 + C_1A_2 = 2 \times 4 + 4 \times 5 + 5 \times 2 = 38$
$(i,j,k)=(2,2,2)$ ： $A_2B_2 + B_2C_2 + C_2A_2 = 2 \times 4 + 4 \times 6 + 6 \times 2 = 44$

将这些值按降序排列为 $(44, 38, 36, 34, 31, 29, 27, 23)$ ，因此从大到小第 $5$ 个的值为 $31$ 。

翻译由 DeepSeek R1 完成

输入解题思路，AI测评打分。不知道怎么写?

首页