← Home
For problem statement at 1000-1999/1200-1299/1210-1219/1215/problemE.txt this is a correct solution, but verifier at 1000-1999/1200-1299/1210-1219/1215/verifierE.go ends with All tests passed can you fix the verifier? package main

import (
	"bufio"
	"fmt"
	"math/bits"
	"os"
)

func readInt(r *bufio.Reader) int {
	var n int
	var c byte
	for {
		c, _ = r.ReadByte()
		if c >= '0' && c <= '9' {
			n = int(c - '0')
			break
		}
	}
	for {
		c, _ = r.ReadByte()
		if c < '0' || c > '9' {
			break
		}
		n = n*10 + int(c-'0')
	}
	return n
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	n := readInt(reader)

	var cnt [20][20]int64
	var counts [20]int64

	for i := 0; i < n; i++ {
		u := readInt(reader) - 1
		for v := 0; v < 20; v++ {
			cnt[v][u] += counts[v]
		}
		counts[u]++
	}

	dp := make([]int64, 1<<20)
	for i := 1; i < (1 << 20); i++ {
		dp[i] = 1e18
	}

	for mask := uint32(0); mask < (1 << 20); mask++ {
		if dp[mask] == 1e18 {
			continue
		}
		for u := 0; u < 20; u++ {
			if (mask & (1 << u)) == 0 {
				var cost int64
				m := mask
				for m > 0 {
					v := bits.TrailingZeros32(m)
					cost += cnt[u][v]
					m &= m - 1
				}
				nxt := mask | (1 << u)
				cand := dp[mask] + cost
				if cand < dp[nxt] {
					dp[nxt] = cand
				}
			}
		}
	}

	fmt.Println(dp[(1<<20)-1])
}