← Home
For problem statement at 0-999/500-599/550-559/552/problemE.txt this is a correct solution, but verifier at 0-999/500-599/550-559/552/verifierE.go ends with All tests passed can you fix the verifier? package main

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

type Start struct {
	u uint64
	v uint64
}

type End struct {
	w uint64
	z uint64
}

type Term struct {
	val    uint64
	starts []Start
	ends   []End
}

type U128 struct {
	hi uint64
	lo uint64
}

func mul64(a, b uint64) U128 {
	hi, lo := bits.Mul64(a, b)
	return U128{hi: hi, lo: lo}
}

func add64(x U128, y uint64) U128 {
	lo, c := bits.Add64(x.lo, y, 0)
	return U128{hi: x.hi + c, lo: lo}
}

func less(a, b U128) bool {
	if a.hi != b.hi {
		return a.hi < b.hi
	}
	return a.lo < b.lo
}

func main() {
	in := bufio.NewReader(os.Stdin)
	var s string
	fmt.Fscan(in, &s)

	terms := make([]Term, 0, (len(s)+1)/2)
	factors := make([]uint64, 0, 16)

	for i := 0; i < len(s); i += 2 {
		factors = append(factors, uint64(s[i]-'0'))
		if i == len(s)-1 || s[i+1] == '+' {
			l := len(factors)
			prefix := make([]uint64, l+1)
			suffix := make([]uint64, l+1)
			prefix[0] = 1
			for j := 0; j < l; j++ {
				prefix[j+1] = prefix[j] * factors[j]
			}
			suffix[l] = 1
			for j := l; j > 0; j-- {
				suffix[j-1] = suffix[j] * factors[j-1]
			}
			starts := make([]Start, l)
			ends := make([]End, l)
			for j := 0; j < l; j++ {
				starts[j] = Start{u: prefix[j], v: suffix[j]}
				ends[j] = End{w: prefix[j+1], z: suffix[j+1]}
			}
			terms = append(terms, Term{
				val:    prefix[l],
				starts: starts,
				ends:   ends,
			})
			factors = factors[:0]
		}
	}

	m := len(terms)
	pref := make([]uint64, m+1)
	for i := 0; i < m; i++ {
		pref[i+1] = pref[i] + terms[i].val
	}
	total := pref[m]

	ans := U128{lo: total}

	for a := 0; a < m; a++ {
		ta := terms[a]
		leftOutside := pref[a]
		for b := a + 1; b < m; b++ {
			tb := terms[b]
			mid := pref[b] - pref[a+1]
			outside := leftOutside + (total - pref[b+1])
			for _, st := range ta.starts {
				base := mid + st.v
				for _, en := range tb.ends {
					mval := base + en.w
					uz := st.u * en.z
					cand := add64(mul64(uz, mval), outside)
					if less(ans, cand) {
						ans = cand
					}
				}
			}
		}
	}

	out := new(big.Int).SetUint64(ans.hi)
	out.Lsh(out, 64)
	out.Add(out, new(big.Int).SetUint64(ans.lo))

	writer := bufio.NewWriter(os.Stdout)
	fmt.Fprintln(writer, out.String())
	writer.Flush()
}