← Home
For problem statement at 0-999/100-199/110-119/111/problemC.txt this is a correct solution, but verifier at 0-999/100-199/110-119/111/verifierC.go ends with All tests passed can you fix the verifier? package main

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

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n, m int
	fmt.Fscan(in, &n, &m)

	w, l := n, m
	if w > l {
		w, l = l, w
	}

	maskCount := 1 << w
	full := maskCount - 1

	pop := make([]int, maskCount)
	dom := make([]int, maskCount)
	for b := 0; b < maskCount; b++ {
		pop[b] = bits.OnesCount(uint(b))
		d := b | ((b << 1) & full) | (b >> 1)
		dom[b] = d
	}

	size := maskCount * maskCount
	valid := make([][]int, size)
	for a := 0; a < maskCount; a++ {
		for b := 0; b < maskCount; b++ {
			idx := a*maskCount + b
			base := dom[b] | a
			for c := 0; c < maskCount; c++ {
				if (base | c) == full {
					valid[idx] = append(valid[idx], c)
				}
			}
		}
	}

	const inf = int(1e9)
	dp := make([]int, size)
	ndp := make([]int, size)
	for i := 0; i < size; i++ {
		dp[i] = inf
		ndp[i] = inf
	}

	for x1 := 0; x1 < maskCount; x1++ {
		dp[x1] = pop[x1]
	}

	for col := 1; col < l; col++ {
		for i := 0; i < size; i++ {
			ndp[i] = inf
		}
		for a := 0; a < maskCount; a++ {
			base := a * maskCount
			for b := 0; b < maskCount; b++ {
				cur := dp[base+b]
				if cur == inf {
					continue
				}
				for _, c := range valid[base+b] {
					idx := b*maskCount + c
					v := cur + pop[c]
					if v < ndp[idx] {
						ndp[idx] = v
					}
				}
			}
		}
		dp, ndp = ndp, dp
	}

	best := inf
	for a := 0; a < maskCount; a++ {
		base := a * maskCount
		for b := 0; b < maskCount; b++ {
			cur := dp[base+b]
			if cur == inf {
				continue
			}
			if (dom[b]|a) == full && cur < best {
				best = cur
			}
		}
	}

	fmt.Fprintln(out, n*m-best)
}