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

import (
	"fmt"
	"io"
	"os"
)

var C [1005][1005][26]int32
var pref [1005][1005]int64

type Query struct {
	a, b, c, d int
	e          byte
}

func main() {
	input, _ := io.ReadAll(os.Stdin)
	idx := 0

	readInt := func() int {
		for idx < len(input) && input[idx] <= ' ' {
			idx++
		}
		if idx >= len(input) {
			return 0
		}
		res := 0
		for idx < len(input) && input[idx] > ' ' {
			res = res*10 + int(input[idx]-'0')
			idx++
		}
		return res
	}

	readByte := func() byte {
		for idx < len(input) && input[idx] <= ' ' {
			idx++
		}
		if idx >= len(input) {
			return 0
		}
		b := input[idx]
		idx++
		return b
	}

	readString := func() []byte {
		for idx < len(input) && input[idx] <= ' ' {
			idx++
		}
		if idx >= len(input) {
			return nil
		}
		start := idx
		for idx < len(input) && input[idx] > ' ' {
			idx++
		}
		return input[start:idx]
	}

	n := readInt()
	m := readInt()
	k := readInt()

	T := make([][]byte, n)
	for i := 0; i < n; i++ {
		T[i] = readString()
	}

	Q := make([]Query, k)
	for i := 0; i < k; i++ {
		a := readInt()
		b := readInt()
		c := readInt()
		d := readInt()
		e := readByte()
		Q[i] = Query{a, b, c, d, e}

		charIdx := e - 'a'
		C[a][b][charIdx]++
		C[c+1][b][charIdx]--
		C[a][d+1][charIdx]--
		C[c+1][d+1][charIdx]++
	}

	for x := 1; x <= n; x++ {
		for y := 1; y <= m; y++ {
			for c := 0; c < 26; c++ {
				C[x][y][c] += C[x-1][y][c] + C[x][y-1][c] - C[x-1][y-1][c]
			}
		}
	}

	var Base int64
	for x := 1; x <= n; x++ {
		for y := 1; y <= m; y++ {
			tChar := int32(T[x-1][y-1] - 'a')
			for c := int32(0); c < 26; c++ {
				if count := C[x][y][c]; count > 0 {
					diff := tChar - c
					if diff < 0 {
						diff = -diff
					}
					Base += int64(count) * int64(diff)
				}
			}
		}
	}

	var term [26][26][26]int32
	var absTargetTChar [26][26]int32
	for target := int32(0); target < 26; target++ {
		for tChar := int32(0); tChar < 26; tChar++ {
			absVal := target - tChar
			if absVal < 0 {
				absVal = -absVal
			}
			absTargetTChar[target][tChar] = absVal
			for c := int32(0); c < 26; c++ {
				ac := target - c
				if ac < 0 {
					ac = -ac
				}
				tc := tChar - c
				if tc < 0 {
					tc = -tc
				}
				at := target - tChar
				if at < 0 {
					at = -at
				}
				term[target][tChar][c] = ac - tc - at
			}
		}
	}

	minDist := int64(-1)

	for target_c := int32(0); target_c < 26; target_c++ {
		hasQuery := false
		for i := 0; i < k; i++ {
			if int32(Q[i].e-'a') == target_c {
				hasQuery = true
				break
			}
		}
		if !hasQuery {
			continue
		}

		for x := 1; x <= n; x++ {
			for y := 1; y <= m; y++ {
				tChar := int32(T[x-1][y-1] - 'a')
				sum := int32(k) * absTargetTChar[target_c][tChar]
				for c := int32(0); c < 26; c++ {
					if count := C[x][y][c]; count > 0 {
						sum += count * term[target_c][tChar][c]
					}
				}
				pref[x][y] = pref[x-1][y] + pref[x][y-1] - pref[x-1][y-1] + int64(sum)
			}
		}

		for i := 0; i < k; i++ {
			if int32(Q[i].e-'a') == target_c {
				change := pref[Q[i].c][Q[i].d] - pref[Q[i].a-1][Q[i].d] - pref[Q[i].c][Q[i].b-1] + pref[Q[i].a-1][Q[i].b-1]
				dist := Base + change
				if minDist == -1 || dist < minDist {
					minDist = dist
				}
			}
		}
	}

	fmt.Println(minDist)
}