← Home
For problem statement at 2000-2999/2000-2099/2020-2029/2021/problemD.txt this is a correct solution, but verifier at 2000-2999/2000-2099/2020-2029/2021/verifierD.go ends with All 6 tests passed. can you fix the verifier? package main

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

var buffer []byte
var head, tail int

func nextInt() int64 {
	for head < tail && buffer[head] <= ' ' {
		head++
	}
	if head >= tail {
		return 0
	}
	sign := int64(1)
	if buffer[head] == '-' {
		sign = -1
		head++
	}
	res := int64(0)
	for head < tail && buffer[head] >= '0' && buffer[head] <= '9' {
		res = res*10 + int64(buffer[head]-'0')
		head++
	}
	return res * sign
}

func main() {
	buffer, _ = io.ReadAll(os.Stdin)
	tail = len(buffer)

	if head >= tail {
		return
	}
	tCases := int(nextInt())

	var P, A_old, B_old, C_old, A_new, B_new, C_new []int64

	for t := 0; t < tCases; t++ {
		n := int(nextInt())
		m := int(nextInt())

		if len(P) < m+1 {
			P = make([]int64, m+1)
			A_old = make([]int64, m+1)
			B_old = make([]int64, m+1)
			C_old = make([]int64, m+1)
			A_new = make([]int64, m+1)
			B_new = make([]int64, m+1)
			C_new = make([]int64, m+1)
		}

		for i := 1; i <= n; i++ {
			P[0] = 0
			for j := 1; j <= m; j++ {
				v := nextInt()
				P[j] = P[j-1] + v
			}

			if i == 1 {
				max_P := int64(-1e18)
				for L := m; L >= 1; L-- {
					if P[L] > max_P {
						max_P = P[L]
					}
					A_old[L] = max_P - P[L-1]
				}
				min_P := int64(1e18)
				for R := 1; R <= m; R++ {
					if P[R-1] < min_P {
						min_P = P[R-1]
					}
					B_old[R] = P[R] - min_P
				}
				for j := 1; j <= m; j++ {
					C_old[j] = A_old[j]
					if B_old[j] > C_old[j] {
						C_old[j] = B_old[j]
					}
				}
			} else {
				for j := 1; j <= m; j++ {
					A_new[j] = -1e18
					B_new[j] = -1e18
					C_new[j] = -1e18
				}

				max_B_minus_P := int64(-1e18)
				max_minus_P := int64(-1e18)
				max_C_plus_max_minus_P := int64(-1e18)

				for R := 1; R <= m; R++ {
					if R >= 2 {
						val1 := max_B_minus_P
						val2 := int64(-1e18)
						if A_old[R] != -1e18 && max_minus_P != -1e18 {
							val2 = A_old[R] + max_minus_P
						}
						val3 := max_C_plus_max_minus_P

						best := val1
						if val2 > best {
							best = val2
						}
						if val3 > best {
							best = val3
						}

						if best != -1e18 {
							B_new[R] = P[R] + best
						}
					}

					if max_minus_P != -1e18 && C_old[R] != -1e18 {
						cand := C_old[R] + max_minus_P
						if cand > max_C_plus_max_minus_P {
							max_C_plus_max_minus_P = cand
						}
					}

					if B_old[R] != -1e18 {
						cand := B_old[R] - P[R-1]
						if cand > max_B_minus_P {
							max_B_minus_P = cand
						}
					}
					cand_minus_P := -P[R-1]
					if cand_minus_P > max_minus_P {
						max_minus_P = cand_minus_P
					}
				}

				max_A_plus_P := int64(-1e18)
				max_P := int64(-1e18)
				max_C_plus_max_P := int64(-1e18)

				for L := m; L >= 1; L-- {
					if L <= m-1 {
						val1 := max_A_plus_P
						val2 := int64(-1e18)
						if B_old[L] != -1e18 && max_P != -1e18 {
							val2 = B_old[L] + max_P
						}
						val3 := max_C_plus_max_P

						best := val1
						if val2 > best {
							best = val2
						}
						if val3 > best {
							best = val3
						}

						if best != -1e18 {
							A_new[L] = -P[L-1] + best
						}
					}

					if max_P != -1e18 && C_old[L] != -1e18 {
						cand := C_old[L] + max_P
						if cand > max_C_plus_max_P {
							max_C_plus_max_P = cand
						}
					}

					if A_old[L] != -1e18 {
						cand := A_old[L] + P[L]
						if cand > max_A_plus_P {
							max_A_plus_P = cand
						}
					}
					if P[L] > max_P {
						max_P = P[L]
					}
				}

				for j := 1; j <= m; j++ {
					A_old[j] = A_new[j]
					B_old[j] = B_new[j]
					C_old[j] = A_new[j]
					if B_new[j] > C_old[j] {
						C_old[j] = B_new[j]
					}
				}
			}
		}

		ans := int64(-1e18)
		for j := 1; j <= m; j++ {
			if B_old[j] > ans {
				ans = B_old[j]
			}
		}
		fmt.Println(ans)
	}
}