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

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

type FastReader struct {
	r *bufio.Reader
}

func NewFastReader() *FastReader {
	return &FastReader{r: bufio.NewReaderSize(os.Stdin, 1<<20)}
}

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

type Pair struct {
	val int
	idx int
}

func main() {
	in := NewFastReader()
	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	t := in.nextInt()
	for ; t > 0; t-- {
		n := in.nextInt()
		m := in.nextInt()
		a := make([][]int, n)
		for i := 0; i < n; i++ {
			row := make([]int, m)
			for j := 0; j < m; j++ {
				row[j] = in.nextInt()
			}
			a[i] = row
		}

		cols := make([]Pair, m)
		for j := 0; j < m; j++ {
			mx := 0
			for i := 0; i < n; i++ {
				if a[i][j] > mx {
					mx = a[i][j]
				}
			}
			cols[j] = Pair{mx, j}
		}
		sort.Slice(cols, func(i, j int) bool { return cols[i].val > cols[j].val })
		k := n
		if m < k {
			k = m
		}
		selected := make([]int, k)
		for i := 0; i < k; i++ {
			selected[i] = cols[i].idx
		}

		full := 1 << n
		const NEG int = -1 << 60
		dp := make([]int, full)
		for i := 1; i < full; i++ {
			dp[i] = NEG
		}

		arr := make([]int, n)
		sums := make([]int, full)
		for _, cj := range selected {
			best := make([]int, full) // initialized to 0
			// For each rotation
			for rot := 0; rot < n; rot++ {
				for i := 0; i < n; i++ {
					idx := i - rot
					if idx < 0 {
						idx += n
					}
					arr[i] = a[idx][cj]
				}
				sums[0] = 0
				for mask := 1; mask < full; mask++ {
					lsb := mask & -mask
					b := bits.TrailingZeros(uint(lsb))
					prev := mask ^ lsb
					sums[mask] = sums[prev] + arr[b]
				}
				for mask := 1; mask < full; mask++ {
					if sums[mask] > best[mask] {
						best[mask] = sums[mask]
					}
				}
			}

			dp2 := make([]int, full)
			copy(dp2, dp)
			for mask := 0; mask < full; mask++ {
				if dp[mask] == NEG {
					continue
				}
				rem := (full - 1) ^ mask
				for sub := rem; sub > 0; sub = (sub - 1) & rem {
					nm := mask | sub
					v := dp[mask] + best[sub]
					if v > dp2[nm] {
						dp2[nm] = v
					}
				}
			}
			dp = dp2
		}

		if k == 0 {
			// No columns, sum is 0
			dp[full-1] = 0
		}
		// Output answer
		out.WriteString(intToString(dp[full-1]))
		out.WriteByte('\n')
	}
}

func intToString(x int) string {
	if x == 0 {
		return "0"
	}
	sign := ""
	if x < 0 {
		sign = "-"
		x = -x
	}
	buf := [20]byte{}
	i := len(buf)
	for x > 0 {
		i--
		buf[i] = byte('0' + x%10)
		x /= 10
	}
	if sign != "" {
		i--
		buf[i] = '-'
	}
	return string(buf[i:])
}