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

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

func main() {
	data, _ := io.ReadAll(os.Stdin)
	p := 0
	nextInt := func() int64 {
		for p < len(data) && (data[p] == ' ' || data[p] == '\n' || data[p] == '\r' || data[p] == '\t') {
			p++
		}
		sign := int64(1)
		if data[p] == '-' {
			sign = -1
			p++
		}
		var v int64
		for p < len(data) && data[p] >= '0' && data[p] <= '9' {
			v = v*10 + int64(data[p]-'0')
			p++
		}
		return sign * v
	}

	n := int(nextInt())
	d := nextInt()

	a := make([]int64, n)
	zeros := make([]int, 0)
	for i := 0; i < n; i++ {
		a[i] = nextInt()
		if a[i] == 0 {
			zeros = append(zeros, i)
		}
	}

	if len(zeros) == 0 {
		var cur int64
		for i := 0; i < n; i++ {
			cur += a[i]
			if cur > d {
				fmt.Print(-1)
				return
			}
		}
		fmt.Print(0)
		return
	}

	m := len(zeros)
	T := make([]int64, m)
	U := make([]int64, m)

	var cur, maxp int64
	for i := 0; i < zeros[0]; i++ {
		cur += a[i]
		if cur > maxp {
			maxp = cur
		}
	}
	if maxp > d {
		fmt.Print(-1)
		return
	}
	sum0 := cur

	for z := 0; z < m; z++ {
		l := zeros[z] + 1
		r := n - 1
		if z+1 < m {
			r = zeros[z+1] - 1
		}
		cur, maxp = 0, 0
		for i := l; i <= r; i++ {
			cur += a[i]
			if cur > maxp {
				maxp = cur
			}
		}
		T[z] = cur
		U[z] = d - maxp
	}

	F := make([]int64, m)
	F[m-1] = U[m-1]
	for i := m - 2; i >= 0; i-- {
		b := F[i+1] - T[i]
		if U[i] < b {
			F[i] = U[i]
		} else {
			F[i] = b
		}
	}
	for i := 0; i < m; i++ {
		if F[i] < 0 {
			fmt.Print(-1)
			return
		}
	}

	ans := 0
	prev := sum0
	if prev > F[0] {
		fmt.Print(-1)
		return
	}
	x := prev
	if x < 0 {
		ans++
		x = F[0]
	}

	for i := 0; i < m-1; i++ {
		prev = x + T[i]
		if prev > F[i+1] {
			fmt.Print(-1)
			return
		}
		x = prev
		if x < 0 {
			ans++
			x = F[i+1]
		}
	}

	fmt.Print(ans)
}