Problem: The Patisserie AtCoder sells cakes with number-shaped candles. There are X, Y and Z kinds of cakes with 1-shaped, 2-shaped and 3-shaped candles, respectively. Each cake has an integer value called _deliciousness_ , as follows:    * The deliciousness of the cakes with 1-shaped candles are A_1, A_2, ..., A_X.   * The deliciousness of the cakes with 2-shaped candles are B_1, B_2, ..., B_Y.   * The deliciousness of the cakes with 3-shaped candles are C_1, C_2, ..., C_Z.  Takahashi decides to buy three cakes, one for each of the three shapes of the candles, to celebrate ABC 123.   There are X \times Y \times Z such ways to choose three cakes.   We will arrange these X \times Y \times Z ways in descending order of the sum of the deliciousness of the cakes.   Print the sums of the deliciousness of the cakes for the first, second, ..., K-th ways in this list.

Submission attempts (in order):
package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
	"sort"
	"strconv"
	"strings"
)

// An Item is something we manage in a priority queue.
type Item struct {
	value    []int
	priority int
	// The index is needed by update and is maintained by the heap.Interface methods.
	index int // The index of the item in the heap.
}

// A PriorityQueue implements heap.Interface and holds Items.
type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
	//We want Pop to give us the highest, not lowest, priority so we use greater than here.
	return pq[i].priority >= pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}

func (pq *PriorityQueue) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Item)
	item.index = n
	*pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	item.index = -1 // for safety
	*pq = old[0 : n-1]
	return item
}

func Equal(a, b []int) bool {
	if len(a) != len(b) {
		return false
	}
	for i, v := range a {
		if v != b[i] {
			return false
		}
	}
	return true
}

var sc = bufio.NewScanner(os.Stdin)

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

func exists(pq PriorityQueue, item *Item) bool {
	for i := 0; i < pq.Len(); i++ {
		if pq[i].priority == item.priority && Equal(pq[i].value, item.value) {
			return true
		}
	}
	return false
}

func main() {
	line1 := nextLine()
	XYZK := strings.Split(line1, " ")
	X, _ := strconv.Atoi(XYZK[0])
	Y, _ := strconv.Atoi(XYZK[1])
	Z, _ := strconv.Atoi(XYZK[2])
	K, _ := strconv.Atoi(XYZK[3])
	line2 := nextLine()
	line3 := nextLine()
	line4 := nextLine()
	a := strings.Split(line2, " ")
	b := strings.Split(line3, " ")
	c := strings.Split(line4, " ")
	A := make([]int, X)
	B := make([]int, Y)
	C := make([]int, Z)

	for i := 0; i < X; i++ {
		A[i], _ = strconv.Atoi(a[i])
	}
	for i := 0; i < Y; i++ {
		B[i], _ = strconv.Atoi(b[i])
	}
	for i := 0; i < Z; i++ {
		C[i], _ = strconv.Atoi(c[i])
	}
	sort.Slice(A, func(i, j int) bool {
		return A[i] >= A[j]
	})
	sort.Slice(B, func(i, j int) bool {
		return B[i] >= B[j]
	})
	sort.Slice(C, func(i, j int) bool {
		return C[i] >= C[j]
	})
	pq := make(PriorityQueue, 1)
	item0 := &Item{
		value:    []int{0, 0, 0},
		priority: A[0] + B[0] + C[0],
		index:    0,
	}
	pq[0] = item0
	heap.Init(&pq)
	ans := make([]int, K)
	for ind := 0; ind < K; ind++ {
		item := heap.Pop(&pq).(*Item)
		p := item.priority
		i := item.value[0]
		j := item.value[1]
		k := item.value[2]
		ans[ind] = p

		if i+1 < X && j < Y && k < Z {
			item1 := &Item{
				value:    []int{i + 1, j, k},
				priority: A[i+1] + B[j] + C[k],
			}
			if !exists(pq, item1) {
				heap.Push(&pq, item1)
			}
		}

		if i < X && j+1 < Y && k < Z {
			item2 := &Item{
				value:    []int{i, j + 1, k},
				priority: A[i] + B[j+1] + C[k],
			}
			if !exists(pq, item2) {
				heap.Push(&pq, item2)
			}
		}

		if i < X && j < Y && k+1 < Z {
			item3 := &Item{
				value:    []int{i, j, k + 1},
				priority: A[i] + B[j] + C[k+1],
			}
			if !exists(pq, item3) {
				heap.Push(&pq, item3)
			}
		}
	}
	for _, v := range ans {
		fmt.Println(v)
	}
}


import heapq
X, Y, Z, K = map(int, input().split())
A = sorted([int(i) for i in input().split()], reverse=True)
B = sorted([int(i) for i in input().split()], reverse=True)
C = sorted([int(i) for i in input().split()], reverse=True)

h = []
heapq.heappush(h, (A[0] + B[0] + C[0], 0, 0, 0))

ans = []
for _ in range(K):
    p, i, j, k = heapq.heappop(h)
    ans.append(p)
    if i + 1 < X and j < Y and k < Z and not (A[i+1] + B[j] + C[k], i + 1, j, k) in h:
        heapq.heappush(h, (A[i + 1] + B[j] + C[k], i + 1, j, k))
    if i < X and j + 1 < Y and k < Z and not (A[i] + B[j+1] + C[k], i, j+1, k) in h:
        heapq.heappush(h, (A[i] + B[j+1] + C[k], i, j+1, k))
    if i < X and j < Y and k + 1 < Z and not (A[i] + B[j] + C[k+1], i, j, k+1) in h:
        heapq.heappush(h, (A[i] + B[j] + C[k+1], i, j, k+1))

for a in ans:
    print(a)

import heapq
X, Y, Z, K = map(int, input().split())
A = sorted([int(i) for i in input().split()], reverse=True)
B = sorted([int(i) for i in input().split()], reverse=True)
C = sorted([int(i) for i in input().split()], reverse=True)

h = []
heapq.heappush(h, (-(A[0] + B[0] + C[0]), (0, 0, 0)))

ans = []
e = set()
for _ in range(K):
    p, v = heapq.heappop(h)
    i, j, k = v
    ans.append(p)
    if i + 1 < X and j < Y and k < Z and not (-(A[i+1] + B[j] + C[k]), (i+1, j, k)) in e:
        heapq.heappush(h, (-(A[i + 1] + B[j] + C[k]), (i+1, j, k)))
        e.add((-(A[i + 1] + B[j] + C[k]), (i+1, j, k)))
    if i < X and j + 1 < Y and k < Z and not (-(A[i] + B[j+1] + C[k]), (i, j+1, k)) in e:
        heapq.heappush(h, (-(A[i] + B[j+1] + C[k]), (i, j+1, k)))
        e.add((-(A[i] + B[j+1] + C[k]), (i, j+1, k)))
    if i < X and j < Y and k + 1 < Z and not (-(A[i] + B[j] + C[k+1]), (i, j, k+1)) in e:
        heapq.heappush(h, (-(A[i] + B[j] + C[k+1]), (i, j, k+1)))
        e.add((-(A[i] + B[j] + C[k+1]), (i, j, k+1)))

for a in ans:
    print(-a)

Verdicts: Runtime Error

Wrong Answer

Accepted