F - K-th Largest Triplet
Source: atcoder
Difficulty: 500

Problem Statement
You are given three integer sequences of length
N
, namely
A=(A_1,A_2,\ldots,A_N)
,
B=(B_1,B_2,\ldots,B_N)
, and
C=(C_1,C_2,\ldots,C_N)
, and an integer
K
.
For each of the
N^3
choices of integers
i,j,k
(
1\leq i,j,k\leq N
), compute the value
A_iB_j + B_jC_k + C_kA_i
. Among all these values, find the
K
-th largest value.
Constraints
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
All input values are integers.
Input
The input is given from Standard Input in the following format:
N
K
A_1
A_2
\ldots
A_N
B_1
B_2
\ldots
B_N
C_1
C_2
\ldots
C_N
Output
Print the answer.
Sample Input 1
2 5
1 2
3 4
5 6
Sample Output 1
31
The
N^3=8
values are computed as follows:
For
(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
For
(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
For
(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
For
(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
For
(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
For
(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
For
(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
For
(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
Sorting these values in descending order, we have
(44,38,36,34,31,29,27,23)
, so the 5th largest value is
31
.
Sample Input 2
3 10
100 100 100
100 100 100
100 100 100
Sample Output 2
30000
Sample Input 3
5 54
800516877 573289179 26509423 168629803 696409999
656737335 915059758 201458890 931198638 185928366
140174496 254538849 830992027 305186313 322164559
Sample Output 3
689589940713840351

C++ solution:
#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<int> A(n), B(n), C(n);
    for (int i = 0; i < n; i++)
    {
        cin >> A[i];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> B[i];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> C[i];
    }

    sort(A.begin(), A.end(), greater());
    sort(B.begin(), B.end(), greater());
    sort(C.begin(), C.end(), greater());

    using Item = tuple<long long, int, int, int, int>;
    priority_queue<Item> pq;

    auto get = [&](int i, int j, int k)
    {
        return 1ll * A[i] * B[j] + 1ll * B[j] * C[k] + 1ll * C[k] * A[i];
    };
    pq.emplace(get(0, 0, 0), 0, 0, 0, 0);

    for (int i = 0; i < k; i++)
    {
        auto [v, x, y, z, t] = pq.top();
        pq.pop();

        if (i == k - 1)
        {
            cout << v << endl;
            return 0;
        }

        if (t == 0 && x + 1 < n)
        {
            pq.emplace(get(x + 1, y, z), x + 1, y, z, 0);
        }
        if (t <= 1 && y + 1 < n)
        {
            pq.emplace(get(x, y + 1, z), x, y + 1, z, 1);
        }
        if (t <= 2 && z + 1 < n)
        {
            pq.emplace(get(x, y, z + 1), x, y, z + 1, 2);
        }
    }

    return 0;
}

Go solution:
package main

import (
	"bufio"
	. "fmt"
	"io"
	"os"
	_ "runtime/debug"
	"sort"
)

// func init() { debug.SetGCPercent(-1) }

func Run(_r io.Reader, _w io.Writer) {
	in := bufio.NewReader(_r)
	out := bufio.NewWriter(_w)
	defer out.Flush()

	var n, k int
	cin(in, &n, &k)
	a := make([]int, n+1)
	b := make([]int, n+1)
	c := make([]int, n+1)
	for i := 1; i <= n; i++ {
		cin(in, &a[i])
	}
	for i := 1; i <= n; i++ {
		cin(in, &b[i])
	}
	for i := 1; i <= n; i++ {
		cin(in, &c[i])
	}
	sort.Slice(a[1:], func(i, j int) bool {
		return a[1:][i] > a[1:][j]
	})
	sort.Slice(b[1:], func(i, j int) bool {
		return b[1:][i] > b[1:][j]
	})
	sort.Slice(c[1:], func(i, j int) bool {
		return c[1:][i] > c[1:][j]
	})
	check := func(x int) bool {
		cnt := 0
		for i := 1; i <= n; i++ {
			if a[i]*b[1]+b[1]*c[1]+c[1]*a[i] < x {
				break
			}
			for j := 1; j <= n; j++ {
				if a[i]*b[j]+b[j]*c[1]+c[1]*a[i] < x {
					break
				}
				for l := 1; l <= n; l++ {
					if a[i]*b[j]+b[j]*c[l]+c[l]*a[i] >= x {
						cnt++
					} else {
						break
					}
					if cnt >= k {
						return true
					}
				}
			}
		}
		return false
	}
	l, r := 1, int(3e18)
	ans := 0
	for l <= r {
		mid := l + (r-l)/2
		if check(mid) {
			l = mid + 1
			ans = mid
		} else {
			r = mid - 1
		}
	}
	cout(out, ans)
}

func main() {
	Run(os.Stdin, os.Stdout)
}

func cin(r io.Reader, a ...interface{}) (n int, err error) {
	return Fscan(r, a...)
}

func coutln(w io.Writer, a ...interface{}) (n int, err error) {
	return Fprintln(w, a...)
}

func cout(w io.Writer, a ...interface{}) (n int, err error) {
	return Fprint(w, a...)
}

type Ordered interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64 |
		~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 |
		~float32 | ~float64 |
		~string
}

func min[T Ordered](vals ...T) T {
	_min := vals[0]
	for _, v := range vals[1:] {
		if v < _min {
			_min = v
		}
	}
	return _min
}

func max[T Ordered](vals ...T) T {
	_max := vals[0]
	for _, v := range vals[1:] {
		if v > _max {
			_max = v
		}
	}
	return _max
}

Java solution:
import java.io.*;
import java.util.*;

public class Main {
    public static int INF = 0x3f3f3f3f, mod = 1000000007, mod9 = 998244353;
    public static void main(String args[]){
        try {
            PrintWriter o = new PrintWriter(System.out);
            boolean multiTest = false;
            // init
            if(multiTest) {
                int t = nextInt(), loop = 0;
                while (loop < t) {loop++;solve(o);}
            } else solve(o);
            o.close();
        } catch (Exception e) {e.printStackTrace();}
    }
    static Integer[] a, b, c;
    static int n, t;
    static void solve(PrintWriter o) {
        try {
            n = nextInt();
            t = nextInt();
            a = new Integer[n];
            b = new Integer[n];
            c = new Integer[n];
            for(int i=0;i<n;i++) a[i] = nextInt();
            for(int i=0;i<n;i++) b[i] = nextInt();
            for(int i=0;i<n;i++) c[i] = nextInt();
            Arrays.sort(a, (x,y)->Integer.compare(y,x));
            Arrays.sort(b, (x,y)->Integer.compare(y,x));
            Arrays.sort(c, (x,y)->Integer.compare(y,x));
            long l = 1l, r = (long)3e18+1;
            while(l < r) {
                long m = (l+r)>>1;
                if(check(m)) l = m+1;
                else r = m;
            }
            o.println(l-1);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
    static boolean check(long m) {
        int cnt = 0;
        for(int i=0;i<n;i++) {
            if(f(i, 0, 0) < m) break;
            for(int j=0;j<n;j++) {
                if(f(i, j, 0) < m) break;
                for(int k=0;k<n;k++) {
                    if(f(i, j, k) >= m) {
                        cnt++;
                        if(cnt >= t) return true;
                    }
                    else break;
                }
            }
        }
        return false;
    }
    static long f(int i, int j, int k) {
        return 1l*a[i]*b[j] + 1l*a[i]*c[k] + 1l*b[j]*c[k];
    }
    public static int lower_bound(Integer[] a, long val){
        int l = 0, r = a.length;
        while(l < r){
            int mid = l + (r - l) / 2;
            if(a[mid] < val) l = mid + 1;
            else r = mid;
        }
        return l;
    }
    public static int lower_bound(List<Integer> li, long val){
        int l = 0, r = li.size();
        while(l < r){
            int mid = l + (r - l) / 2;
            if(li.get(mid) < val) l = mid + 1;
            else r = mid;
        }
        return l;
    }
    public static int upper_bound(long[] preSum, long val){
        int l = 0, r = preSum.length;
        while(l < r){
            int mid = l + (r - l) / 2;
            if(preSum[mid] <= val) l = mid + 1;
            else r = mid;
        }
        return l;
    }
    public static int upper_bound(List<int[]> li, long val){
        int l = 0, r = li.size();
        while(l < r){
            int mid = l + (r - l) / 2;
            if(li.get(mid)[0] <= val) l = mid + 1;
            else r = mid;
        }
        return l;
    }
    public static int upper_bound(List<Integer> li, int val){
        int l = 0, r = li.size();
        while(l < r){
            int mid = l + (r - l) / 2;
            if(li.get(mid) <= val) l = mid + 1;
            else r = mid;
        }
        return l;
    }
    public static int upper_bound(int[] a, long val){
        int l = 0, r = a.length;
        while(l < r){
            int mid = l + (r - l) / 2;
            if(a[mid] <= val) l = mid + 1;
            else r = mid;
        }
        return l;
    }
    public static int lower_bound(List<int[]> li, int val){
        int l = 0, r = li.size();
        while(l < r){
            int mid = l + (r - l) / 2;
            if(li.get(mid)[0] < val) l = mid + 1;
            else r = mid;
        }
        return l;
    }
    public static int lower_bound(int[] a, int val){
        int l = 0, r = a.length;
        while(l < r){
            int mid = l + (r - l) / 2;
            if(a[mid] < val) l = mid + 1;
            else r = mid;
        }
        return l;
    }
    public static int lower_bound(long[][] a, long val){
        int l = 0, r = a.length;
        while(l < r){
            int mid = l + (r - l) / 2;
            if(a[mid][0] < val) l = mid + 1;
            else r = mid;
        }
        return l;
    }
    public static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a%b);
    }
    public static long[] extgcd(long a, long b) {
        if(b == 0) return new long[]{1, 0};
        long[] it = extgcd(b, a%b);
        long x = it[1], y = it[0];
        y -= a/b*x;
        return new long[]{x, y};
    }
    public static long lcm(long a, long b){
        return a / gcd(a,b)*b;
    }
    public static long qpow(long a, long n){
        long ret = 1l;
        while(n > 0){
            if((n & 1) == 1) ret = ret * a;
            n >>= 1;
            a = a * a;
        }
        return ret;
    }
    public static long qpow(long a, long n, int md){
        a %= md;
        long ret = 1l;
        while(n > 0){
            if((n & 1) == 1) ret = ret * a % md;
            n >>= 1;
            a = a * a % md;
        }
        return ret;
    }
    public static class FenWick {
        int n;
        long[] a;
        long[] tree;
        public FenWick(int n){
            this.n = n;
            a = new long[n+1];
            tree = new long[n+1];
        }
        private void add(int x, long val){
            while(x <= n){
                tree[x] += val;
                x += x&-x;
            }
        }
        private void addMx(int x, long val) {
            a[x] += val;
            tree[x] = a[x];
            while(x <= n) {
                for(int i=1;i<(x&-x);i<<=1) tree[x] = Math.max(tree[x], tree[x-i]);
                x += x&-x;
            }
        }
        private void addMn(int x, long val) {
            a[x] += val;
            tree[x] = a[x];
            while(x <= n) {
                for(int i=1;i<(x&-x);i<<=1) tree[x] = Math.min(tree[x], tree[x-i]);
                x += x&-x;
            }
        }
        private long query(int x){
            long ret = 0l;
            while(x > 0){
                ret += tree[x];
                x -= x&-x;
            }
            return ret;
        }
        private long queryMx(int l, int r) {
            long res = 0l;
            while(l <= r) {
                if(r-(r&-r) >= l) {
                    res = Math.max(res, tree[r]);
                    r -= r&-r;
                }
                else {
                    res = Math.max(res, a[r]);
                    r--;
                }
            }
            return res;
        }
        private long queryMn(int l, int r) {
            long res = 1l<<55;
            while(l <= r) {
                if(r-(r&-r) >= l) {
                    res = Math.min(res, tree[r]);
                    r -= r&-r;
                }
                else {
                    res = Math.min(res, a[r]);
                    r--;
                }
            }
            return res;
        }
    }
    static class Pair {
        Integer p1, p2;
        public Pair(Integer p1, Integer p2) {
            this.p1 = p1;
            this.p2 = p2;
        }
        @Override
        public int hashCode() {
            int prime = 31, ret = 0;
            ret = ret*prime+p1.hashCode();
            ret = ret*prime+p2.hashCode();
            return ret;
        }
        @Override
        public boolean equals(Object o) {
            if(o instanceof Pair pair) {
                return p1.equals(pair.p1) && p2.equals(pair.p2);
            }
            return false;
        }
    }
    static class DSU {
        int[] parent;
        int[] size;
        public DSU(int n) {
            parent = new int[n];
            size = new int[n];
            for(int i=0;i<n;i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }
        public int find(int x) {
            if(parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        }
        public void union(int x, int y) {
            int root_x = find(x);
            int root_y = find(y);
            if(root_x == root_y) return;
            parent[root_x] = root_y;
            size[root_y] += size[root_x];
            size[root_x] = 0;
        }
    }
    private static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer tokenizer = new StringTokenizer("");
    private static String next() throws IOException{
        while(!tokenizer.hasMoreTokens()){tokenizer = new StringTokenizer(reader.readLine());}
        return tokenizer.nextToken();
    }
    public static int nextInt() throws IOException {return Integer.parseInt(next());}
    public static Long nextLong() throws IOException {return Long.parseLong(next());}
    public static double nextDouble() throws IOException {return Double.parseDouble(next());}
    public static char nextChar() throws IOException {return next().toCharArray()[0];}
    public static String nextString() throws IOException {return next();}
    public static String nextLine() throws IOException {return reader.readLine();}
}

JavaScript solution:
"use strict";
var input=require("fs").readFileSync("/dev/stdin","utf8");
var cin=input.split(/ |\n/),cid=0;
function next(){return +cin[cid++];}
function nextstr(){return cin[cid++];}
function nextbig(){return BigInt(cin[cid++]);}
function nexts(n,a){return a?cin.slice(cid,cid+=n):cin.slice(cid,cid+=n).map(a=>+a);}
function nextssort(n,a){return a?cin.slice(cid,cid+=n).map(a=>+a).sort((a,b)=>b-a):cin.slice(cid,cid+=n).map(a=>+a).sort((a,b)=>a-b);}
function nextm(h,w,a){var r=[],i=0;if(a)for(;i<h;i++)r.push(cin.slice(cid,cid+=w));else for(;i<h;i++)r.push(cin.slice(cid,cid+=w).map(a=>+a));return r;}
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill().map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill().map(x=>"+r+")";return eval(r);}
var streams=[];function print(s){streams.push(s);}

class priorityQueue{
  constructor(){
    this.a=[];
  }
  push(num,inc){
    const a = this.a;
    for(var i = a.length, j; i; i = j){
      j = i - 1 >> 1;
      if(a[j][0] <= num)break;
      a[i] = a[j];
    }
    a[i] = [num,inc];
  }
  pop(){
    const a = this.a, r = a[0], x = a.pop(), k = a.length >> 1;
    for(var i = 0, j; i < k; i = j){
      j = (i << 1) + 1;
      if(a[j+1] && a[j+1][0] < a[j][0])j++;
      if(x[0] <= a[j][0])break;
      a[i] = a[j];
    }
    if(a.length)a[i] = x;
    return r;
  }
  pushpop(num,inc){
    const a = this.a, r = a[0], k = a.length >> 1;
    if(!a.length || r[0] >= num)return [num,inc];
    for(var i = 0, j; i < k; i = j){
      j = (i << 1) + 1;
      if(a[j+1] && a[j+1][0] < a[j][0])j++;
      if(num <= a[j][0])break;
      a[i] = a[j];
    }
    a[i] = [num,inc];
    return r;
  }
  poppush(num,inc){
    const a = this.a, r = a[0], k = a.length >> 1;
    for(var i = 0, j; i < k; i = j){
      j = (i << 1) + 1;
      if(a[j+1] && a[j+1][0] < a[j][0])j++;
      if(num <= a[j][0])break;
      a[i] = a[j];
    }
    a[i] = [num,inc];
    return r;
  }
  get size(){
    return this.a.length;
  }
  get top(){
    return this.a[0];
  }
}

var myOut = main();
if(myOut !== undefined)console.log(String(myOut));
if(streams.length)console.log(streams.join("\n"));

function main(){
  var q = 1;
  while(q--)print(solve());
}

function solve(){
  var [n,k] = nexts(2);
  var a = new Int32Array(n);
  for(var i = 0; i < n; i++){
    a[i] = next();
  }
  a.sort((a,b)=>b-a);
  var b = new Int32Array(n);
  for(var i = 0; i < n; i++){
    b[i] = next();
  }
  b.sort((a,b)=>b-a);
  var c = new Int32Array(n);
  for(var i = 0; i < n; i++){
    c[i] = next();
  }
  c.sort((a,b)=>b-a);
  var pq = new priorityQueue();
  var se = new Set();
  add(0,0,0);
  while(--k){
    var [x,y] = pq.pop();
    var u = g(y);
    for(var i = 0; i < 3; i++){
      u[i]++;
      if(u[i] < n)add(...u);
      u[i]--;
    }
  }
  return -pq.top[0];
  function add(x,y,z){
    var s = f(x,y,z);
    if(se.has(s))return;
    var t = mul(x,y,z);
    se.add(s);
    pq.push(-t,s);
  }
  function mul(x,y,z){
    var xx = BigInt(a[x]);
    var yy = BigInt(b[y]);
    var zz = BigInt(c[z]);
    return xx*(yy+zz) + yy*zz;
  }
  function f(x,y,z){
    return (x*n+y)*n+z;
  }
  function g(p){
    var z = p % n;
    var y = Math.floor(p/n) % n;
    var x = Math.floor(p/(n*n));
    return [x,y,z];
  }
}

Python solution:
import sys; input=sys.stdin.readline
from heapq import*

N, K = map(int, input().split())
A = sorted(map(int, input().split()), reverse=1)
B = sorted(map(int, input().split()), reverse=1)
C = sorted(map(int, input().split()), reverse=1)

p = 10**6
def enc(i, j, k):
  return i*(p**2) + j*p + k
def dec(x):
  i, x = divmod(x, p**2)
  j, k = divmod(x, p)
  return i, j, k
def calc(a, b, c):
  return a*b + b*c + c*a

hq = []
heappush(hq, (-calc(A[0], B[0], C[0]), enc(0, 0, 0)))
vis = set([0])
for _ in range(K):
  ans, x = heappop(hq)
  i, j, k = dec(x)
  if i+1 < N and (x:=enc(i+1, j, k)) not in vis:
    vis.add(x)
    heappush(hq, (-calc(A[i+1], B[j], C[k]), enc(i+1, j, k)))
  if j+1 < N and (y:=enc(i, j+1, k)) not in vis:
    vis.add(y)
    heappush(hq, (-calc(A[i], B[j+1], C[k]), enc(i, j+1, k)))
  if k+1 < N and (z:=enc(i, j, k+1)) not in vis:
    vis.add(z)
    heappush(hq, (-calc(A[i], B[j], C[k+1]), enc(i, j, k+1)))

print(-ans)

Ruby solution:
class PQ
	def initialize
		@h = [] # max-heap
	end

	def enq d,a
		@h << [d,a]
		up_heap
	end
	def deq
		return unless @h[0]
		@h[0],@h[-1] = @h[-1],@h[0]
		d,a = @h.pop
		dn_heap if @h[0]
		return d,a
	end
 
private
	def up_heap
		d, = up = @h[i=@h.size-1]
		while 0<i
			iP = (i-1)/2
			break if d<=@h[iP][0]
			@h[i],i = @h[iP],iP
		end
		@h[i] = up
	end
	def dn_heap
		d, = dn = @h[i=0]
		z = @h.size
		until z <= iC = i+i+1
			iC += 1 if iC+1<z && @h[iC][0]<@h[iC+1][0]
			break if @h[iC][0]<=d
			@h[i],i = @h[iC],iC
		end
		@h[i] = dn
	end
end

(N,K),A,B,C = $<.map{|ln| ln.split.map(&:to_i) }
A.sort!
B.sort!
C.sort!
U = {}
T = lambda{|i,j,k|
	ijk = i*N*N+j*N+k
	U[ijk] = A[i]*B[j]+B[j]*C[k]+C[k]*A[i] if 0<=i && 0<=j && 0<=k && ! U[ijk]
}
Q = PQ.new
Q.enq T[N-1,N-1,N-1],[N-1]*3
t = nil
K.times{
	t,(i,j,k),t1 = Q.deq
	Q.enq t1,[i-1,j,k] if t1 = T[i-1,j,k]
	Q.enq t1,[i,j-1,k] if t1 = T[i,j-1,k]
	Q.enq t1,[i,j,k-1] if t1 = T[i,j,k-1]
}
p t