← Home
For problem statement at 1000-1999/1700-1799/1730-1739/1730/problemF.txt this is a correct solution, but verifier at 1000-1999/1700-1799/1730-1739/1730/verifierF.go ends with All 100 tests passed can you fix the verifier? package main

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

func main() {
	reader := bufio.NewReader(os.Stdin)
	var n, k int
	fmt.Fscan(reader, &n, &k)

	p := make([]int, n)
	idx := make([]int, n+2)
	for i := 0; i < n; i++ {
		fmt.Fscan(reader, &p[i])
		idx[p[i]] = i + 1
	}

	pref := make([][]int16, n+2)
	for i := range pref {
		pref[i] = make([]int16, n+1)
	}
	for m := 1; m <= n; m++ {
		for i := 1; i <= n; i++ {
			pref[m][i] = pref[m-1][i]
		}
		for i := idx[m]; i <= n; i++ {
			pref[m][i]++
		}
	}

	dp := make([][]int, n+2)
	for i := range dp {
		dp[i] = make([]int, 1<<k)
		for j := range dp[i] {
			dp[i][j] = 1e9
		}
	}
	dp[1][0] = 0

	for P := 0; P < n; P++ {
		for m := 1; m <= P+1; m++ {
			if m > n {
				continue
			}
			for mask := 0; mask < (1 << k); mask++ {
				if m-1+bits.OnesCount(uint(mask)) != P {
					continue
				}
				if dp[m][mask] >= 1e9 {
					continue
				}

				c := 0
				for (mask & (1 << c)) != 0 {
					c++
				}
				m_next := m + 1 + c
				mask_next := mask >> (c + 1)

				picked_larger := 0
				for i := 0; i < k; i++ {
					if (mask & (1 << i)) != 0 {
						if m+1+i <= n && idx[m+1+i] < idx[m] {
							picked_larger++
						}
					}
				}
				cost := idx[m] - 1 - int(pref[m-1][idx[m]-1]) - picked_larger
				if dp[m][mask]+cost < dp[m_next][mask_next] {
					dp[m_next][mask_next] = dp[m][mask] + cost
				}

				for j := 0; j < k; j++ {
					x := m + 1 + j
					if x <= n && (mask&(1<<j)) == 0 {
						m_next2 := m
						mask_next2 := mask | (1 << j)

						picked_larger2 := 0
						for i := 0; i < k; i++ {
							if (mask & (1 << i)) != 0 {
								if m+1+i <= n && idx[m+1+i] < idx[x] {
									picked_larger2++
								}
							}
						}
						cost2 := idx[x] - 1 - int(pref[m-1][idx[x]-1]) - picked_larger2
						if dp[m][mask]+cost2 < dp[m_next2][mask_next2] {
							dp[m_next2][mask_next2] = dp[m][mask] + cost2
						}
					}
				}
			}
		}
	}

	fmt.Println(dp[n+1][0])
}