← 返回题目列表

AtCoder · abc391_f

I. 第 K 个最大三元组

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

给定三个长度的整数序列 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.

对于每个 N^3 整数的选择 i,j,k (1\leq i,j,k\leq N),计算值 A_iB_j + B_jC_k + C_kA_i。在所有这些值中,找到 K- 第一个最大值。

约束

  • 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
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

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

的 树的 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.


示例输入 2

3 10
100 100 100
100 100 100
100 100 100

示例输出 2

30000

示例输入 3

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

示例输出 3

689589940713840351