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:])
}