import scala.collection.mutable import scala.collection.mutable.ArrayBuffer import scala.io.StdIn.* import scala.math.* import scala.reflect.ClassTag import scala.util.chaining.* trait Monoid[T]: val zero: T def plus(left: T, right: T): T inline given Monoid[Long] with override val zero = 0L override def plus(left: Long, right: Long) = max(left, right) class BinaryIndexedTree[T : ClassTag](val size: Int)(using m: Monoid[T]): export m.* private val vec = Array.fill(size){zero} def get(position: Int): T = var result = zero var pos = position while vec.indices.contains(pos) do result = plus(result, vec(pos)) pos -= ~pos & (pos + 1) result def add(position: Int, value: T): Unit = var pos = position while vec.indices.contains(pos) do vec(pos) = plus(vec(pos), value) pos += ~pos & (pos + 1) def getAll(): T = get(size - 1) extension (array: Array[Int]) def lowerBound(value: Int): Int = var min = 0 var max = array.length while min < max do val mid = (min + max) >>> 1 if array(mid) < value then min = mid + 1 else max = mid max @main def main = val n = readLine().toInt val fruits = Array.fill(n){ val Array(t, x, v) = readLine().split(' ').map(_.toInt) (t, x, v) } val diff = fruits.map{(t, x, _) => t - x}.distinct.sorted val bit = BinaryIndexedTree[Long](diff.length) for (t, x, v) <- fruits.sorted(using Ordering.by[(Int, Int, Int), Int]{(t, x, _) => t + x}.orElseBy{(t, _, _) => t}) do if t >= abs(x) then val di = diff.lowerBound(t - x) val maxValue = bit.get(di) + v bit.add(di, maxValue) val result = bit.getAll() println(result)