题目详情题解（0）讨论（0）提交记录（0）

AT_utpc2023_k.Kth Sum

通过率：0%

AC君温馨提醒

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

题目描述

给定三个长度为 NN 的整数序列 (A1,A2,…,AN),(B1,B2,…,BN),(C1,C2,…,CN)(A_1, A_2, \dots, A_N), (B_1, B_2, \dots, B_N), (C_1, C_2, \dots, C_N)。

对于所有满足 1≤i≤N,1≤j≤N,1≤k≤N1 \leq i \leq N, 1 \leq j \leq N, 1 \leq k \leq N 的整数 i,j,ki, j, k 的选取方法，共有 N3N^3 种。对于每种情况，计算 Ai+Bj+CkA_i + B_j + C_k 的值。请你求出这些值中第 KK 小的值。

输入格式

输入以如下形式从标准输入读入：

NN KK A1A_1 A2A_2 …\dots ANA_N B1B_1 B2B_2 …\dots BNB_N C1C_1 C2C_2 …\dots CNC_N

输出格式

请输出一个整数，表示答案。

输入输出样例

  • 输入#1

    2 4
1 2
3 4
5 6

    输出#1

    10

  • 输入#2

    10 40
11 9 13 12 15 11 11 2 11 17
3 1 10 2 12 18 9 11 11 15
14 9 4 14 16 9 20 2 1 18

    输出#2

    14

  • 输入#3

    1 1
1000000000
1000000000
1000000000

    输出#3

    3000000000

说明/提示

样例解释 1

所有 i,j,ki, j, k 的选择方式共有 88 种。对应的 Ai+Bj+CkA_i+B_j+C_k 的值按从小到大为 9,10,10,10,11,11,11,129, 10, 10, 10, 11, 11, 11, 12，其中第 44 小的值是 1010。

数据范围

  • 所有输入均为整数。
  • 1≤N≤500001 \leq N \leq 50000
  • 1≤K≤min⁡{N3,109}1 \leq K \leq \min\lbrace N^3, 10^9\rbrace
  • 0≤Ai≤1090 \leq A_i \leq 10^9
  • 0≤Bj≤1090 \leq B_j \leq 10^9
  • 0≤Ck≤1090 \leq C_k \leq 10^9

由 ChatGPT 5 翻译

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

首页