← Home
For problem statement at 0-999/600-699/610-619/616/problemF.txt this is a correct solution, but verifier at 0-999/600-699/610-619/616/verifierF.go ends with REFERENCE_SOURCE_PATH environment variable not set
exit status 1 can you fix the verifier? package main

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

type State struct {
	len  int32
	link int32
	next [26]int32
}

var st []State
var sz int32

func extend(last int32, c int) int32 {
	if q := st[last].next[c]; q != 0 {
		if st[q].len == st[last].len+1 {
			return q
		}
		clone := sz
		sz++
		st = append(st, State{
			len:  st[last].len + 1,
			link: st[q].link,
			next: st[q].next,
		})
		for p := last; p != -1 && st[p].next[c] == q; p = st[p].link {
			st[p].next[c] = clone
		}
		st[q].link = clone
		return clone
	}

	cur := sz
	sz++
	st = append(st, State{
		len:  st[last].len + 1,
		link: -1,
	})
	p := last
	for p != -1 && st[p].next[c] == 0 {
		st[p].next[c] = cur
		p = st[p].link
	}
	if p == -1 {
		st[cur].link = 0
	} else {
		q := st[p].next[c]
		if st[q].len == st[p].len+1 {
			st[cur].link = q
		} else {
			clone := sz
			sz++
			st = append(st, State{
				len:  st[p].len + 1,
				link: st[q].link,
				next: st[q].next,
			})
			for p != -1 && st[p].next[c] == q {
				st[p].next[c] = clone
				p = st[p].link
			}
			st[q].link = clone
			st[cur].link = clone
		}
	}
	return cur
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Buffer(make([]byte, 1024*1024), 10*1024*1024)
	scanner.Split(bufio.ScanWords)

	if !scanner.Scan() {
		return
	}
	n, _ := strconv.Atoi(scanner.Text())

	stringsList := make([]string, n)
	for i := 0; i < n; i++ {
		scanner.Scan()
		stringsList[i] = scanner.Text()
	}

	costs := make([]int64, n)
	for i := 0; i < n; i++ {
		scanner.Scan()
		cVal, _ := strconv.ParseInt(scanner.Text(), 10, 64)
		costs[i] = cVal
	}

	st = make([]State, 0, 1000005)
	st = append(st, State{len: 0, link: -1})
	sz = 1

	for _, t := range stringsList {
		var last int32 = 0
		for i := 0; i < len(t); i++ {
			last = extend(last, int(t[i]-'a'))
		}
	}

	val := make([]int64, sz)
	for i, t := range stringsList {
		var curr int32 = 0
		for j := 0; j < len(t); j++ {
			curr = st[curr].next[t[j]-'a']
			val[curr] += costs[i]
		}
	}

	var maxLen int32 = 0
	for i := int32(1); i < sz; i++ {
		if st[i].len > maxLen {
			maxLen = st[i].len
		}
	}

	c := make([]int32, maxLen+1)
	for i := int32(1); i < sz; i++ {
		c[st[i].len]++
	}
	for i := int32(1); i <= maxLen; i++ {
		c[i] += c[i-1]
	}

	order := make([]int32, sz-1)
	for i := int32(1); i < sz; i++ {
		c[st[i].len]--
		order[c[st[i].len]] = i
	}

	var ans int64 = 0
	for i := len(order) - 1; i >= 0; i-- {
		u := order[i]
		p := st[u].link
		if p != -1 {
			val[p] += val[u]
		}
		cand := int64(st[u].len) * val[u]
		if cand > ans {
			ans = cand
		}
	}

	fmt.Println(ans)
}