← Home
For problem statement at 0-999/900-999/940-949/949/problemD.txt this is a correct solution, but verifier at 0-999/900-999/940-949/949/verifierD.go ends with All tests passed can you fix the verifier? package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	reader := bufio.NewReader(os.Stdin)
	var n, d, b int
	if _, err := fmt.Fscanf(reader, "%d %d %d\n", &n, &d, &b); err != nil {
		return
	}

	a := make([]int, n+1)
	for i := 1; i <= n; i++ {
		fmt.Fscanf(reader, "%d", &a[i])
	}

	pref := make([]int, n+2)
	for i := 1; i <= n; i++ {
		pref[i] = pref[i-1] + a[i]
	}
	suff := make([]int, n+2)
	for i := n; i >= 1; i-- {
		suff[i] = suff[i+1] + a[i]
	}

	L := (n + 1) / 2
	R := n / 2

	min := func(x, y int) int {
		if x < y {
			return x
		}
		return y
	}
	max := func(x, y int) int {
		if x > y {
			return x
		}
		return y
	}

	max1 := L
	for j1 := 1; j1 <= L; j1++ {
		r := min(n, j1*(d+1))
		max1 = min(max1, L-j1+pref[r]/b)
	}

	max2 := R
	for j2 := L + 1; j2 <= n; j2++ {
		l := max(1, j2-d*(n-j2+1))
		max2 = min(max2, j2-(L+1)+suff[l]/b)
	}

	check := func(ans int) bool {
		Y1 := max(0, L-ans)
		Y2 := max(0, R-ans)

		if Y1 > max1 || Y2 > max2 {
			return false
		}

		for j1 := 1; j1 <= L; j1++ {
			for j2 := L + 1; j2 <= n; j2++ {
				r := min(n, j1*(d+1))
				l := max(1, j2-d*(n-j2+1))
				if r < l {
					req := max(0, Y1-L+j1) + max(0, Y2-j2+L+1)
					if req > (pref[r]+suff[l])/b {
						return false
					}
				}
			}
		}
		return true
	}

	left, right := 0, max(L, R)
	res := right
	for left <= right {
		mid := (left + right) / 2
		if check(mid) {
			res = mid
			right = mid - 1
		} else {
			left = mid + 1
		}
	}

	fmt.Println(res)
}