← 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"
	"fmt"
	"os"
	"sort"
	"strconv"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1024*1024), 10*1024*1024)

	scanInt := func() int {
		scanner.Scan()
		res, _ := strconv.Atoi(scanner.Text())
		return res
	}

	if !scanner.Scan() {
		return
	}
	t, _ := strconv.Atoi(scanner.Text())

	for tc := 0; tc < t; tc++ {
		n := scanInt()
		m := scanInt()

		mat := make([][]int, n)
		for i := 0; i < n; i++ {
			mat[i] = make([]int, m)
			for j := 0; j < m; j++ {
				mat[i][j] = scanInt()
			}
		}

		type Column struct {
			maxVal int
			data   []int
		}

		cols := make([]Column, m)
		for j := 0; j < m; j++ {
			cols[j].data = make([]int, n)
			maxV := -1
			for i := 0; i < n; i++ {
				cols[j].data[i] = mat[i][j]
				if mat[i][j] > maxV {
					maxV = mat[i][j]
				}
			}
			cols[j].maxVal = maxV
		}

		sort.Slice(cols, func(i, j int) bool {
			return cols[i].maxVal > cols[j].maxVal
		})

		k := m
		if k > n {
			k = n
		}
		cols = cols[:k]

		maxValArray := make([][]int, k)
		for c := 0; c < k; c++ {
			maxValArray[c] = make([]int, 1<<n)
			for mask := 0; mask < (1 << n); mask++ {
				bestSum := 0
				for s := 0; s < n; s++ {
					currentSum := 0
					for i := 0; i < n; i++ {
						if ((mask >> i) & 1) == 1 {
							currentSum += cols[c].data[(i+s)%n]
						}
					}
					if currentSum > bestSum {
						bestSum = currentSum
					}
				}
				maxValArray[c][mask] = bestSum
			}
		}

		dp := make([]int, 1<<n)
		for c := 0; c < k; c++ {
			for mask := (1 << n) - 1; mask >= 0; mask-- {
				for submask := mask; submask > 0; submask = (submask - 1) & mask {
					val := dp[mask^submask] + maxValArray[c][submask]
					if val > dp[mask] {
						dp[mask] = val
					}
				}
			}
		}

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