import kotlin.math.absoluteValue class MaxBit(val size: Int) { private val array = LongArray(size){0} fun get(position: Int): Long { var result = 0L var pos = position while (pos in array.indices) { result = maxOf(result, array[pos]) pos -= pos.inv() and (pos + 1) } return result } fun add(position: Int, value: Long) { var pos = position while (pos in array.indices) { array[pos] = maxOf(array[pos], value) pos += pos.inv() and (pos + 1) } } fun getAll(): Long = get(size - 1) } fun List.lowerBound(value: Int): Int { var min = 0 var max = size while (min < max) { val mid = (min + max) ushr 1 if (this[mid] < value) { min = mid + 1 }else { max = mid } } return max } fun main() { val n = readLine()!!.toInt() val fruits = List(n){ val (t, x, v) = readLine()!!.split(' ').map(String::toInt) Triple(t, x, v) } val diff = fruits.map { (t, x, _) -> t - x}.distinct().sorted() val bit = MaxBit(diff.size) for ((t, x, v) in fruits.sortedWith(compareBy> { (t, x, _) -> t + x}.thenBy { (t, _, _) -> t })) { if (t < x.absoluteValue) continue val di = diff.lowerBound(t - x) val maxValue = bit.get(di) + v bit.add(di, maxValue) } val result = bit.getAll() println(result) }