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

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

func main() {
	in := bufio.NewReader(os.Stdin)
	var n int
	if _, err := fmt.Fscan(in, &n); err != nil {
		return
	}
	a := make([]int32, n)
	pref := make([]int32, n+1)
	for i := 0; i < n; i++ {
		fmt.Fscan(in, &a[i])
		pref[i+1] = pref[i] + a[i]
	}

	sumRange := func(i, j int) int32 {
		if i > j {
			return 0
		}
		return pref[j+1] - pref[i]
	}

	const OFFSET = 120
	active := make([][240][4]uint32, 110)
	reachableStates := make([][]uint16, n+1)

	active[0][OFFSET][0] |= (1 << 1)

	for l := 0; l <= n; l++ {
		var states []uint16
		for d_idx := 0; d_idx < 240; d_idx++ {
			for w := 0; w < 4; w++ {
				mask := active[l%110][d_idx][w]
				for mask > 0 {
					tz := bits.TrailingZeros32(mask)
					mask ^= (1 << tz)
					k := w*32 + tz

					states = append(states, uint16((d_idx<<8)|k))

					d := d_idx - OFFSET
					L := (l + d) / 2
					R := l - L

					if d <= 0 {
						if L+k <= n && l+k <= n && d_idx+k < 240 {
							active[(l+k)%110][d_idx+k][k/32] |= (1 << (k % 32))
						}
						if L+k+1 <= n && l+k+1 <= n && d_idx+k+1 < 240 {
							active[(l+k+1)%110][d_idx+k+1][(k+1)/32] |= (1 << ((k + 1) % 32))
						}
					} else {
						if R+k <= n && l+k <= n && d_idx-k >= 0 {
							active[(l+k)%110][d_idx-k][k/32] |= (1 << (k % 32))
						}
						if R+k+1 <= n && l+k+1 <= n && d_idx-k-1 >= 0 {
							active[(l+k+1)%110][d_idx-k-1][(k+1)/32] |= (1 << ((k + 1) % 32))
						}
					}
				}
				active[l%110][d_idx][w] = 0
			}
		}
		reachableStates[l] = states
	}

	dp := make([][240][130]int32, 110)

	for l := n; l >= 0; l-- {
		for _, state := range reachableStates[l] {
			d_idx := int(state >> 8)
			k := int(state & 0xFF)
			d := d_idx - OFFSET
			L := (l + d) / 2
			R := l - L

			if d <= 0 {
				val := int32(-2e9)
				canMove := false
				if L+k <= n && l+k <= n && d_idx+k < 240 {
					canMove = true
					v := sumRange(L, L+k-1) + dp[(l+k)%110][d_idx+k][k]
					if v > val {
						val = v
					}
				}
				if L+k+1 <= n && l+k+1 <= n && d_idx+k+1 < 240 {
					canMove = true
					v := sumRange(L, L+k) + dp[(l+k+1)%110][d_idx+k+1][k+1]
					if v > val {
						val = v
					}
				}
				if !canMove {
					val = 0
				}
				dp[l%110][d_idx][k] = val
			} else {
				val := int32(2e9)
				canMove := false
				if R+k <= n && l+k <= n && d_idx-k >= 0 {
					canMove = true
					v := -sumRange(n-R-k, n-R-1) + dp[(l+k)%110][d_idx-k][k]
					if v < val {
						val = v
					}
				}
				if R+k+1 <= n && l+k+1 <= n && d_idx-k-1 >= 0 {
					canMove = true
					v := -sumRange(n-R-k-1, n-R-1) + dp[(l+k+1)%110][d_idx-k-1][k+1]
					if v < val {
						val = v
					}
				}
				if !canMove {
					val = 0
				}
				dp[l%110][d_idx][k] = val
			}
		}
	}

	fmt.Println(dp[0][OFFSET][1])
}