package main import ( "bufio" "fmt" "os" "sort" ) func main() { in := bufio.NewReader(os.Stdin) out := bufio.NewWriter(os.Stdout) defer out.Flush() var n int fmt.Fscan(in, &n) goods := make([][3]int, n) // time, pos, score for i := 0; i < n; i++ { fmt.Fscan(in, &goods[i][0], &goods[i][1], &goods[i][2]) } txs := make([][3]int, 0, n) set := map[int]struct{}{0: {}} // start pos for i := 0; i < n; i++ { t, x, s := goods[i][0], goods[i][1], goods[i][2] if abs(x) <= t { // reachable txs = append(txs, [3]int{t + x, t - x, s}) set[t-x] = struct{}{} } } sort.Slice(txs, func(i, j int) bool { if txs[i][0] == txs[j][0] { return txs[i][1] < txs[j][1] } return txs[i][0] < txs[j][0] }) sorted := make([]int, 0, len(set)) for k := range set { sorted = append(sorted, k) } sort.Ints(sorted) mp := make(map[int]int, len(sorted)) for i, v := range sorted { mp[v] = i } seg := NewFenwickTreePrefix(len(sorted)) seg.Set(0, 0) for i := 0; i < len(txs); i++ { x, s := txs[i][1], txs[i][2] pos := mp[x] curMax := seg.Query(pos+1) + s seg.Set(pos, curMax) } fmt.Fprintln(out, seg.Query(len(sorted))) } func abs(x int) int { if x < 0 { return -x } return x } type S = int const INF int = 1e18 func (*FenwickTreePrefix) e() S { return -INF } func (*FenwickTreePrefix) op(a, b S) S { return max(a, b) } func max(a, b int) int { if a > b { return a } return b } func min(a, b int) int { if a < b { return a } return b } type FenwickTreePrefix struct { n int data []S } func NewFenwickTreePrefix(n int) *FenwickTreePrefix { res := &FenwickTreePrefix{n, make([]S, n+1)} for i := 0; i < n+1; i++ { res.data[i] = res.e() } return res } func NewFenwickTreePrefixWithSlice(nums []S) *FenwickTreePrefix { n := len(nums) res := &FenwickTreePrefix{n, make([]S, n+1)} for i := n; i > 0; i-- { res.data[i] = res.op(res.data[i], nums[i-1]) if p := i + (i & -i); p <= n { res.data[p] = res.op(res.data[p], res.data[i]) } } return res } // 单点更新index处的元素. // 0 <= index < n func (f *FenwickTreePrefix) Set(index int, value S) { for index++; index <= f.n; index += index & -index { f.data[index] = f.op(f.data[index], value) } } // 查询前缀区间 [0,right) 的值. // 0 <= right <= n func (f *FenwickTreePrefix) Query(right int) S { res := f.e() if right > f.n { right = f.n } for ; right > 0; right -= right & -right { res = f.op(res, f.data[right]) } return res }