Use this to learn the idea, then write your own version.
1package main2 3import (4 "bufio"5 . "fmt"6 "io"7)8 910type seg83 []struct {11 l, r int12 val int6413}14 15func (t seg83) build(o, l, r int) {16 t[o].l, t[o].r = l, r17 if l == r {18 return19 }20 m := (l + r) >> 121 t.build(o<<1, l, m)22 t.build(o<<1|1, m+1, r)23}24 25func (t seg83) update(o, i int, val int64) {26 if t[o].l == t[o].r {27 t[o].val = val28 return29 }30 m := (t[o].l + t[o].r) >> 131 if i <= m {32 t.update(o<<1, i, val)33 } else {34 t.update(o<<1|1, i, val)35 }36 t[o].val = max83(t[o<<1].val, t[o<<1|1].val)37}38 39func (t seg83) query(o, l, r int) (res int64) {40 if l <= t[o].l && t[o].r <= r {41 return t[o].val42 }43 m := (t[o].l + t[o].r) >> 144 if r <= m {45 return t.query(o<<1, l, r)46 }47 if m < l {48 return t.query(o<<1|1, l, r)49 }50 return max83(t.query(o<<1, l, r), t.query(o<<1|1, l, r))51}52 53func CF1483C(_r io.Reader, out io.Writer) {54 in := bufio.NewReader(_r)55 var n, v int56 Fscan(in, &n)57 posL := make([]int, n)58 type pair struct{ v, i int }59 s := []pair{{0, -1}}60 for i := range posL {61 Fscan(in, &v)62 for s[len(s)-1].v > v {63 s = s[:len(s)-1]64 }65 posL[i] = s[len(s)-1].i66 s = append(s, pair{v, i})67 }68 69 dp := make([]int64, n)70 t := make(seg83, 4*n)71 t.build(1, 1, n)72 for i, l := range posL {73 if Fscan(in, &v); i == 0 {74 dp[i] = int64(v)75 } else if l < 0 {76 dp[i] = max83(0, t.query(1, 1, i)) + int64(v)77 } else {78 dp[i] = max83(dp[l], t.query(1, l+1, i)+int64(v))79 }80 t.update(1, i+1, dp[i])81 }82 Fprint(out, dp[n-1])83}84 85func max83(a, b int64) int64 {86 if a > b {87 return a88 }89 return b90}91 9293