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

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

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	in := bufio.NewReaderSize(os.Stdin, 1<<20)

	var n, a, b int
	fmt.Fscan(in, &n)
	fmt.Fscan(in, &a, &b)

	h := make([]int, n)
	sum := 0
	for i := 0; i < n; i++ {
		fmt.Fscan(in, &h[i])
		sum += h[i]
	}

	if sum > a+b {
		fmt.Println(-1)
		return
	}

	limit := min(a, sum)
	low := sum - b
	if low < 0 {
		low = 0
	}
	if low > limit {
		fmt.Println(-1)
		return
	}

	const INF int = 1 << 60

	dpR := make([]int, limit+1)
	dpG := make([]int, limit+1)
	for i := 0; i <= limit; i++ {
		dpR[i] = INF
		dpG[i] = INF
	}

	if h[0] <= limit {
		dpR[h[0]] = 0
	}
	dpG[0] = 0

	prefix := h[0]

	for i := 1; i < n; i++ {
		c := min(h[i-1], h[i])

		newR := make([]int, limit+1)
		newG := make([]int, limit+1)
		for j := 0; j <= limit; j++ {
			newR[j] = INF
			newG[j] = INF
		}

		maxPrev := prefix
		if maxPrev > limit {
			maxPrev = limit
		}

		for red := 0; red <= maxPrev; red++ {
			if dpR[red] != INF {
				if red+h[i] <= limit && dpR[red] < newR[red+h[i]] {
					newR[red+h[i]] = dpR[red]
				}
				if dpR[red]+c < newG[red] {
					newG[red] = dpR[red] + c
				}
			}
			if dpG[red] != INF {
				if red+h[i] <= limit && dpG[red]+c < newR[red+h[i]] {
					newR[red+h[i]] = dpG[red] + c
				}
				if dpG[red] < newG[red] {
					newG[red] = dpG[red]
				}
			}
		}

		dpR, dpG = newR, newG
		prefix += h[i]
	}

	ans := INF
	for red := low; red <= limit; red++ {
		if dpR[red] < ans {
			ans = dpR[red]
		}
		if dpG[red] < ans {
			ans = dpG[red]
		}
	}

	if ans == INF {
		fmt.Println(-1)
	} else {
		fmt.Println(ans)
	}
}