← Home
For problem statement at 1000-1999/1300-1399/1310-1319/1312/problemE.txt this is a correct solution, but verifier at 1000-1999/1300-1399/1310-1319/1312/verifierE.go ends with All 100 tests passed can you fix the verifier? package main

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

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

	const INF int = 1 << 30
	val := make([][]int, n)
	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		val[i] = make([]int, n)
		dp[i] = make([]int, n)
		for j := 0; j < n; j++ {
			val[i][j] = -1
			dp[i][j] = INF
		}
		val[i][i] = a[i]
		dp[i][i] = 1
	}

	for length := 2; length <= n; length++ {
		for i := 0; i+length-1 < n; i++ {
			j := i + length - 1
			for k := i; k < j; k++ {
				if val[i][k] != -1 && val[k+1][j] != -1 && val[i][k] == val[k+1][j] {
					val[i][j] = val[i][k] + 1
					break
				}
			}
			if val[i][j] != -1 {
				dp[i][j] = 1
			}
			for k := i; k < j; k++ {
				s := dp[i][k] + dp[k+1][j]
				if s < dp[i][j] {
					dp[i][j] = s
				}
			}
		}
	}

	out := bufio.NewWriter(os.Stdout)
	fmt.Fprintln(out, dp[0][n-1])
	out.Flush()
}