← Home
For problem statement at 0-999/900-999/990-999/999/problemF.txt this is a correct solution, but verifier at 0-999/900-999/990-999/999/verifierF.go ends with All tests passed can you fix the verifier? package main

import (
	"bufio"
	"fmt"
	"os"
)

type FastScanner struct {
	r *bufio.Reader
}

func (fs *FastScanner) NextInt() int {
	sign, val := 1, 0
	c, err := fs.r.ReadByte()
	for (c < '0' || c > '9') && c != '-' {
		c, err = fs.r.ReadByte()
		if err != nil {
			return 0
		}
	}
	if c == '-' {
		sign = -1
		c, _ = fs.r.ReadByte()
	}
	for c >= '0' && c <= '9' {
		val = val*10 + int(c-'0')
		c, err = fs.r.ReadByte()
		if err != nil {
			break
		}
	}
	if err == nil {
		_ = fs.r.UnreadByte()
	}
	return sign * val
}

func main() {
	in := &FastScanner{r: bufio.NewReaderSize(os.Stdin, 1<<20)}
	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	n := in.NextInt()
	k := in.NextInt()
	total := n * k

	const maxV = 100000
	cardCnt := make([]int, maxV+1)
	favCnt := make([]int, maxV+1)

	for i := 0; i < total; i++ {
		x := in.NextInt()
		cardCnt[x]++
	}
	for i := 0; i < n; i++ {
		x := in.NextInt()
		favCnt[x]++
	}

	h := make([]int, k+1)
	for i := 1; i <= k; i++ {
		h[i] = in.NextInt()
	}

	const neg = -1000000000
	dp := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, total+1)
		for j := 0; j <= total; j++ {
			dp[i][j] = neg
		}
	}
	dp[0][0] = 0

	for i := 1; i <= n; i++ {
		limit := i * k
		prevLimit := (i - 1) * k
		for j := 0; j <= limit; j++ {
			best := neg
			maxTake := k
			if j < maxTake {
				maxTake = j
			}
			for t := 0; t <= maxTake; t++ {
				if j-t > prevLimit {
					continue
				}
				val := dp[i-1][j-t] + h[t]
				if val > best {
					best = val
				}
			}
			dp[i][j] = best
		}
	}

	ans := 0
	for v := 1; v <= maxV; v++ {
		if favCnt[v] == 0 {
			continue
		}
		a := favCnt[v]
		b := cardCnt[v]
		if b > a*k {
			b = a * k
		}
		ans += dp[a][b]
	}

	fmt.Fprint(out, ans)
}