← Home
For problem statement at 1000-1999/1500-1599/1540-1549/1542/problemD.txt this is a correct solution, but verifier at 1000-1999/1500-1599/1540-1549/1542/verifierD.go ends with All tests passed can you fix the verifier? package main

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

const MOD = 998244353

type Element struct {
	isPlus bool
	val    int
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	var n int
	if _, err := fmt.Fscan(reader, &n); err != nil {
		return
	}

	A := make([]Element, n)
	for i := 0; i < n; i++ {
		var op string
		fmt.Fscan(reader, &op)
		if op == "+" {
			var val int
			fmt.Fscan(reader, &val)
			A[i] = Element{isPlus: true, val: val}
		} else {
			A[i] = Element{isPlus: false}
		}
	}

	ans := 0

	for i := 0; i < n; i++ {
		if !A[i].isPlus {
			continue
		}

		dp := make([]int, n+1)
		nextDp := make([]int, n+1)
		dp[0] = 1

		for j := 0; j < i; j++ {
			for c := 0; c <= n; c++ {
				nextDp[c] = 0
			}

			if A[j].isPlus {
				if A[j].val > A[i].val || (A[j].val == A[i].val && j > i) {
					for c := 0; c <= n; c++ {
						nextDp[c] = (dp[c] * 2) % MOD
					}
				} else {
					for c := 0; c <= n; c++ {
						nextDp[c] = (nextDp[c] + dp[c]) % MOD
						if c+1 <= n {
							nextDp[c+1] = (nextDp[c+1] + dp[c]) % MOD
						}
					}
				}
			} else {
				for c := 0; c <= n; c++ {
					nextDp[c] = (nextDp[c] + dp[c]) % MOD
					if c > 0 {
						nextDp[c-1] = (nextDp[c-1] + dp[c]) % MOD
					} else {
						nextDp[0] = (nextDp[0] + dp[0]) % MOD
					}
				}
			}
			dp, nextDp = nextDp, dp
		}

		suf := make([]int, n+1)
		nextSuf := make([]int, n+1)
		suf[0] = 1

		for j := n - 1; j > i; j-- {
			for k := 0; k <= n; k++ {
				nextSuf[k] = 0
			}

			if A[j].isPlus {
				if A[j].val > A[i].val || (A[j].val == A[i].val && j > i) {
					for k := 0; k <= n; k++ {
						nextSuf[k] = (suf[k] * 2) % MOD
					}
				} else {
					for k := 0; k <= n; k++ {
						nextSuf[k] = (nextSuf[k] + suf[k]) % MOD
						if k > 0 {
							nextSuf[k-1] = (nextSuf[k-1] + suf[k]) % MOD
						} else {
							nextSuf[0] = (nextSuf[0] + suf[0]) % MOD
						}
					}
				}
			} else {
				for k := 0; k <= n; k++ {
					nextSuf[k] = (nextSuf[k] + suf[k]) % MOD
					if k+1 <= n {
						nextSuf[k+1] = (nextSuf[k+1] + suf[k]) % MOD
					}
				}
			}
			suf, nextSuf = nextSuf, suf
		}

		totalWays := 0
		for c := 0; c <= n; c++ {
			for k := 0; k <= c; k++ {
				ways := (dp[c] * suf[k]) % MOD
				totalWays = (totalWays + ways) % MOD
			}
		}

		totalWays = (totalWays * (A[i].val % MOD)) % MOD
		ans = (ans + totalWays) % MOD
	}

	fmt.Println(ans)
}